题目描述
题目要求将一堆硬币尽可能公平地分给两个人，即两人所得金额之差最小。硬币不能拆分。输出最小差值。
输入格式
第一行一个整数nnn，表示测试用例的数量。每个测试用例第一行一个整数mmm（0≤m≤1000 \le m \le 1000≤m≤100），表示硬币数量。第二行mmm个整数，表示每枚硬币的面值（111到500500500）。
输出格式
对于每个测试用例，输出一行一个整数，表示两人所得金额的最小差值。
样例
输入
2 3 2 3 5 4 1 2 4 6输出
0 1题目分析
本题的核心是子集和问题（subset sum\texttt{subset sum}subset sum）。设总金额为SSS，一人分得xxx，另一人分得S−xS - xS−x，差值为∣S−2x∣|S - 2x|∣S−2x∣。最小化差值等价于找到最接近S/2S/2S/2的子集和。
动态规划
使用0/1\texttt{0/1}0/1背包，dp[j]\textit{dp}[j]dp[j]表示能否凑出金额jjj。初始化dp[0]=true\textit{dp}[0] = \texttt{true}dp[0]=true，然后对每个硬币进行更新。最后从⌊S/2⌋\lfloor S/2 \rfloor⌊S/2⌋向下找到第一个可凑出的金额，差值即为S−2×targetS - 2 \times targetS−2×target。
复杂度分析
总金额≤100×500=50000\le 100 \times 500 = 50000≤100×500=50000，m≤100m \le 100m≤100，时间复杂度O(m×S)O(m \times S)O(m×S)，空间O(S)O(S)O(S)。
代码实现
// Dividing coins// UVa ID: 562// Verdict: Accepted// Submission Date: 2016-08-16// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcoins[110],cents[25010],n,m;cin>>n;for(intc=1;c<=n;c++){inttotal=0;cin>>m;for(inti=1;i<=m;i++){cin>>coins[i];total+=coins[i];}if(m<=1){cout<<total<<'\n';continue;}inthalf=total/2;memset(cents,0,sizeof(cents));for(inti=1;i<=m;i++)for(intj=half;j>=coins[i];j--)cents[j]=max(cents[j],cents[j-coins[i]]+coins[i]);for(inti=half;i>=1;i--)if(cents[i]){cout<<abs(total-2*cents[i])<<'\n';break;}}return0;}
