boj 343

Description
Tradia最近去了趟超市，采购了好多好吃的东西，其中花花绿绿的巧克力最是诱人。为了感谢Jim前段时间对自己的帮助，Tradia决定把自己的巧克力分一些给Jim。但是Tradia也爱吃巧克力，她不想把自己全部的巧克力都给Jim，而是把巧克力平均分配，使得给Jim的总量和留给自己的总量之差最小。聪明的你能帮助她吗？

Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=50)，表示总共有T组测试数据。
接下来是每组测试数据，第一行是一个数N(N<=20)，表示一共有N个巧克力。接着是这N个巧克力的描述，用一个正数M(M<=10000)表示巧克力的质量。


Output
首先，输出Case #X：其中X代表是第X组数据(具体格式参照样例)。
然后输出每组数据的答案，即最小差值。


Sample Input

2
1
5
2
2 3


Sample Output

Case #1:
5
Case #2:
1


Source
humanjustic@Fourth

思路：

转换为0-1背包求解

代码：

#include<iostream>
using namespace std;
int dp[100005];
int arr[25];
int main()
{int t;scanf("%d",&t);for(int k=1;k<=t;k++){int n,sum = 0;scanf("%d",&n);memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){scanf("%d",&arr[i]);sum+=arr[i];}int v = sum/2;for(int i=0;i<n;i++)for(int j=v;j>=arr[i];j--)dp[j] = max(dp[j-arr[i]]+arr[i],dp[j]);printf("Case #%d:\n%d\n",k,abs(sum-2*dp[v]));}
}