正整数分组--01背包+dp

第1行：一个数N，N为正整数的数量。 第2 - N+1行，N个正整数。 (N <= 100, 所有正整数的和 <= 10000) 输出 输出这个最小差 输入示例 5 1 2 3 4 5 输出示例 1 http://www.51nod.com/tutorial/course.html#!courseId=7 要使和的差值最小，两组数都要尽可能接近总和的一半，转化为背包问题，就是用这些数尽可能大的填充sum/2 #include <cstdio> #include<algorithm> #include<cstring> using namespace std; int main() { int n; int dp[10007];//要足够大 int sum; int a[107]; int other; while(~scanf("%d",&n)) { sum = 0; for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); sum += a[i]; } memset(dp,0,sizeof(dp)); for(int i = 1;i <= n;i++) for(int j = sum/2;j >= a[i];j--) dp[j] = max(dp[j],dp[j-a[i]]+a[i]); other = sum - dp[sum/2]; int ss=other-dp[sum/2]; printf("%d\n",ss>0?ss:-ss); } return 0; }