❀ 題目傳送門 ❀

https://atcoder.jp/contests/dp/tasks/dp_d

❀ 解題小技巧 ❀

就是背包問題。
…
…好像有點不負責任w \

核心觀念

首先要先有兩個陣列分別儲存「物品價值」跟「物品重量」（下面分別為 v 跟 w）
再來就是 dp 陣列，其中 dp[i] 的意思為背包限重為i時，所能拿的最大價值。
接著要用for迴圈跑過每一個物品，並決定要不要拿（最外圈是選定一個物品，第二圈是決定在當前重量要不要拿）。 \

轉移式

讓我們來看看轉移式：
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
對，他比較難懂一點，讓我們慢慢來。
如果拿了東西，那價值就會增加v[i]，但同時重量也得花掉w[i]。
換句話說，若拿了東西，問題可以改想為：限重為當前重量-w[i]，的最佳策略。
因而得出dp[j-w[i]] + v[i]

轉移式疑問

那為什麼要跟dp[j]比誰大？
當拿到第i個物品的時候，就要對dp[限重] ~ dp[w[i]]檢查數值是否更新
也就是，拿了東西會不會比不拿還大，若比較大則更新，較小則不更新。
「海星海星，你腦袋還好吧，不拿怎麼會比拿還大」 但是答案是對的，所以就這樣吧
是因為第i圈的dp[j]意思是，我們拿了i個物品後，背包限重為j時，所能拿的最大值。　
舉個淺例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原題目：
重量：１　２　３
價值：３　２　１
限重：３

第　2　圈時，dp 已解決兩物品：
重量：１　２
價值：３　２
dp[3] 此時為 5 （背包限重為３時，所能拿的最大值，當前情況是是全拿）

第　3　圈時：
檢查第三個物品的重量為　3
若拿了　dp[0] + 1 => 0 + 1 => 1（dp[0]也就是限重0，當然不可能拿任何東西，因此價值為0）
若不拿　dp[3] => 5（從上一圈更新）

所以我們會比較的是已經挑過i - 1物品最划算的背包，跟現在拿了比較誰價值更高
而不是空空如也的背包，跟現在拿了比較誰價值更高 \

補充

這邊有個細節：dp[限重] ~ dp[w[i]]而不是dp[w[i]] ~ dp[限重]
至於為什麼，等到出現無限背包問題再說吧！

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define burst ios::sync_with_stdio(0); cin.tie(0);
 
signed main(){
  burst
  int N, W;
  int v[105], w[105], dp[100005];
  cin >> N >> W;
  for(int i = 1; i <= N; i++){
    cin >> w[i] >> v[i];
  }
  memset(dp, 0, sizeof(dp));
  for(int i = 1; i <= N; i++){
    for(int j = W; j >= w[i]; j--){
      dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }
  cout << dp[W];
  return 0;
}