题目链接：https://vjudge.net/contest/103424#problem/E
题目大意：
给你一堆硬币，让你分成两堆，分别给A，B两个人，求两人得到的最小差。
解题思路：
求解两人分得钱币的最小差值，巧妙地转化为01背包问题。
sum代表这堆钱币的总价值，ans=sum/2，求出得钱较少的人的钱币总量，即在这堆钱币中挑选出一定量的钱币，使得它的总值为小于或等于ans的最大值，即将它转化为01背包问题，背包容量为ans,每一个钱币看成价值与体积相等的物品。
#include <bits/stdc++.h>
using namespace std; int dp[int(5e4+)]; int main(){
int n,T;scanf("%d",&T);
while(T--){
memset(dp,,sizeof(dp));
int arr[];int sum=;
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&arr[i]),sum+=arr[i];
int cur=sum/; //将总值均分成两部分
for(int i=;i<=n;i++){
for(int j=cur;j>=arr[i];j--){
dp[j]=max(dp[j],dp[j-arr[i]]+arr[i]);
}
}
printf("%d\n",sum-*dp[cur]);
}
}
2018-04-29