alan23273850 的刷題筆記
d637: 路過的鴨duck
Tags: knapsack
出處：https://zerojudge.tw/ShowProblem?problemid=d637
提交：https://zerojudge.tw/Submissions?problemid=d637&account=allllllan123456
問題：給你 n 個物品各自的重量 $\in[1,100]$ 與價值 $\in[1,5000]$，請問應該選入哪些物品到限重 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]={0}, n; cin >> n;
6 while (n--) {
7 int w, v; cin >> w >> v;
8 for (int i=100; i>=w; i--)
9 if (dp[i-w] + v > dp[i])
10 dp[i] = dp[i-w] + v;
11 }
12 cout << dp[100] << '\n';
13 return 0;
14}