题目描述题目要求将一堆硬币尽可能公平地分给两个人即两人所得金额之差最小。硬币不能拆分。输出最小差值。输入格式第一行一个整数nnn表示测试用例的数量。每个测试用例第一行一个整数mmm0≤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×50050000\le 100 \times 500 50000≤100×50050000m≤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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcoins[110],cents[25010],n,m;cinn;for(intc1;cn;c){inttotal0;cinm;for(inti1;im;i){cincoins[i];totalcoins[i];}if(m1){couttotal\n;continue;}inthalftotal/2;memset(cents,0,sizeof(cents));for(inti1;im;i)for(intjhalf;jcoins[i];j--)cents[j]max(cents[j],cents[j-coins[i]]coins[i]);for(intihalf;i1;i--)if(cents[i]){coutabs(total-2*cents[i])\n;break;}}return0;}
