alan23273850 的刷題筆記
a276: 又分糖果囉
Tags: subset-sum
出處：https://zerojudge.tw/ShowProblem?problemid=a276
提交：https://zerojudge.tw/Submissions?problemid=a276&account=allllllan123456
問題：給定 $n\in[1,20]$ 個數字 $\in[1,1000000]$，問你把這些數字「盡量平分 (總和)」為兩堆之後它們的差距 (最小) 是多少。
解法：此乃子集和問題，先算出總和 S 之後把這些數字用最佳策略塞進容量 S/2 的箱子內，那最後此箱子內的總體積就是其中一堆的和。唯一要注意的是這題不能用背包問題的 DP 方法，因為 1000000 實在是太大了，不論在時間或空間都是一種傷害，而且只有 20 個數字，因此 DFS 比較合理。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n, totalsum, maX, m[20];
5
6void dfs(int index, int sum) {
7 if (sum > totalsum / 2) return;
8 if (sum > maX) maX = sum;
9 if (index == n) return;
10 dfs(index+1, sum + m[index]);
11 dfs(index+1, sum);
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
15 while (cin >> n) {
16 maX = INT_MIN; totalsum = 0;
17 for (int i=0; i<n; i++)
18 cin >> m[i], totalsum += m[i];
19 dfs(0, 0);
20 cout << (totalsum-maX) - maX << '\n';
21 }
22 return 0;
23}