alan23273850 的刷題筆記
d390: 00562 - Dividing coins
Tags: subset-sum
出處：https://zerojudge.tw/ShowProblem?problemid=d390
提交：https://zerojudge.tw/Submissions?problemid=d390&account=allllllan123456
問題：給定 $m\in[0,100]$ 個數字 $\in[1,500]$，問你把這些數字「盡量平分 (總和)」為兩堆之後它們的差距 (最小) 是多少。
解法：此乃子集和問題，先算出總和 S 之後把這些數字用最佳策略塞進容量 S/2 的箱子內，那最後此箱子內的總體積就是其中一堆的和。數字多但總容量低，很適合用背包問題的 DP 算法。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int T; cin >> T;
6 while (T--) {
7 int v[100], dp[25001]={0}, sum=0, m; cin >> m;
8 for (int i=0; i<m; i++)
9 cin >> v[i], sum += v[i];
10 for (int i=0; i<m; i++)
11 for (int j=sum/2; j>=v[i]; j--)
12 dp[j] = max(dp[j], dp[j-v[i]] + v[i]);
13 cout << (sum-dp[sum/2]) - dp[sum/2] << '\n';
14 }
15 return 0;
16}