2109 - 分糖果
时间限制 : 1 秒
内存限制 : 32 MB
小明和小红有一些糖果，现在他们决定分配这些糖果。他们共有N个糖果，每个糖果的重量在1~100克之间（包括1克和100克）。
小明和小红任何一人都不能接受对方分配到的糖果的重量更大，所以两人各分配到的糖果的重量必须相同，如果有剩下的，则送给其他人。在两人各分配到的糖果重量相同的前提下，他们还想要分配到的糖果重量尽可能的大。
现在给你N个糖果的重量，请你计算他们必须送给别人多少克的糖果，以此来满足他们自己分配糖果的要求。
友情提示：糖果不能切开来分！并且可能存在两人都分不到糖果的情况哦。
题目输入
输入包含多组测试数据。
每组输入的第一行是一个整数N（0<=N<=20），表示糖果的个数，当N=0时，输入结束。
接下来N行，每行输入一个整数，表示一个糖果的重量。
题目输出
对于每组输入，输出一个整数，表示必须送给别人的糖果的重量，以此来满足他们自己的分配要求。
输入/输出样例
输入格式
5 1 2 3 2 1 0
输出格式
1
C语言解答
#include<stdio.h> #include<math.h> int a[25]; int s[25]; int max; void dp(int n,int m,int num) { if (!m) { if (max < num) max = num; } if (n<0 || fabs(m)>s[n] || num+s[n]<max) return ; dp(n-1,m+a[n],num+a[n]); dp(n-1,m-a[n],num+a[n]); dp(n-1,m,num); } int main() { int n; int i; while (scanf("%d",&n),n) { for (i=0; i<n; i++) { scanf("%d",a+i); if (!i) s[i] = a[i]; else s[i] = s[i-1] + a[i]; } max = 0; dp(n-1,0,0); printf("%d\n",s[n-1]-max); } return 0; }
C++解答
#include <stdio.h> #include <math.h> int a[25], sv[25], maxi; void dfs(int r, int d, int bv) { if (!d) { if (bv > maxi) maxi = bv; } if (r < 0 || fabs(d) > sv[r] || bv + sv[r] < maxi) return; dfs(r - 1, d + a[r], bv + a[r]); dfs(r - 1, d - a[r], bv + a[r]); dfs(r - 1, d, bv); } int main() { int n, i; while (scanf("%d", &n) != EOF, n) { for (i = 0; i < n; i++) { scanf("%d", &a[i]); if (!i) sv[i] = a[i]; else sv[i] = sv[i - 1] + a[i]; } maxi = 0; dfs(n - 1, 0, 0); printf("%d\n", sv[n - 1] - maxi); } return 0; }