alan23273850 的刷題筆記
d862: NOIP2001 4.装箱问题
Tags: subset-sum
出處：https://zerojudge.tw/ShowProblem?problemid=d862
提交：https://zerojudge.tw/Submissions?problemid=d862&account=allllllan123456
問題：給你 $n\in[1,30]$ 個物品各自的體積，請問應該選入哪些物品到容量 $V\in[0,20000]$ 的箱子中才能使得剩餘空間最小？
解法：此乃 0/1 背包問題的應用，只要讓每個物品的價值就剛好等於它們各自的體積，就能套用它的模型了。
心得：這題物品數量少，可能有人會想使用 DFS，這題也會 AC，但是效率仍然不及 knapsack DP，像我就花了 31 ms。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int dp[20001] = {0};
6 int V, n; cin >> V >> n;
7 for (int v; cin >> v;)
8 for (int i=V; i>=v; i--)
9 if (dp[i-v] + v > dp[i])
10 dp[i] = dp[i-v] + v;
11 cout << V - dp[V] << '\n';
12 return 0;
13}