alan23273850 的刷題筆記
a587: 祖靈好孝順 ˋˇˊ
Tags: knapsack
出處：https://zerojudge.tw/ShowProblem?problemid=a587
提交：https://zerojudge.tw/Submissions?problemid=a587&account=allllllan123456
問題：給你 $n\in[1,100]$ 個物品各自的重量與價值 $\in[0,2000]$，請問應該選入哪些物品到限重 $W\in[1,10000]$ 的背包裡面才能最大化背包的價值？
解法：經典背包問題，可參閱本站對於該問題的解析。這題可惜的地方在於背包限重是在給完所有物品的資訊之後才提供的，就沒辦法像經典演算法那樣邊給邊算。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int N, W, w[100], v[100], dp[10001] = {0};
6 while (cin >> N) { memset(dp, 0, sizeof dp);
7 for (int i=0; i<N; i++) cin >> w[i] >> v[i];
8 cin >> W;
9 for (int i=0; i<N; i++)
10 for (int j=W; j>=w[i]; j--)
11 if (dp[j-w[i]] + v[i] > dp[j])
12 dp[j] = dp[j-w[i]] + v[i];
13 cout << dp[W] << '\n';
14 }
15 return 0;
16}