容易的ACM搜索题

简单的ACM搜索题
描述 
今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？ 
输入 
多组测试数据（<=1500）。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量

输出 
输出分成两堆后的质量差 
样例输入 
5
5 8 13 27 14

[解决办法]
其实不简单..ACM是个好东西...顶起..
[解决办法]
看编程之美，数组划分问题。
[解决办法]
想错了，这个不要求两堆个数相等。
[解决办法]
直接背包问题，以总重量/2作为背包容量。

bool dp[i][j]=dp[i+1][j-weight[i]] || dp[i+1][j];

dp[i][j]表示i...n这些西瓜能否凑出j重量。

初始化就是初始化dp[n][1...totalWeight/2]。
[解决办法]

C/C++ code

#include <iostream>using namespace std;const int N=20;const int W=10000;bool dp[N+1][W];int weight[N+1];int main(){    int n,w=0;    cin>>n;    for(int i=1;i<=N;++i)    {        cin>>weight[i];        w+=weight[i];    }    for(int j=0;j<=W/2;++j)    {        dp[n][j]=false;        if(weight[n]==j)        {            dp[n][j]=true;        }    }    for(int i=n-1;i>=1;--i)    {        for(int j=w/2;j>=0;--j)        {            dp[i][j]=dp[i+1][j];            if(j>=weight[i])            {                dp[i][j]=dp[i][j]||dp[i+1][j-weight[i]];            }        }    }    int result;    for(int j=w/2;j>=0;--j)    {                if(dp[1][j])        {            result=j;            break;        }    }    cout<<(w-result)-result<<endl;    return 0;}