alan23273850 的刷題筆記
b184: 5. 裝貨櫃問題
Tags: knapsack
出處：https://zerojudge.tw/ShowProblem?problemid=b184
提交：https://zerojudge.tw/Submissions?problemid=b184&account=allllllan123456
問題：給你一些物品各自的重量 $\in[1,100]$ 與價值 $\in[1,60000]$，請問應該選入哪些物品到限重 100 的背包中才能最大化背包的價值？
解法：經典背包問題，可參閱本站對於該問題的解析。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int dp[101], n;
6 while (cin >> n) {
7 memset(dp, 0, sizeof dp);
8 while (n--) {
9 int w, v; cin >> w >> v;
10 for (int i=100; i>=w; i--)
11 if (dp[i-w] + v > dp[i])
12 dp[i] = dp[i-w] + v;
13 }
14 cout << dp[100] << '\n';
15 }
16 return 0;
17}