【模板】01背包 題目鏈接

題目描述 :

輸入描述:

輸出描述:

示例1

輸入

3 5
2 10
4 5
1 4

輸出

14
9

說明

裝第一個和第三個物品時總價值最大，但是裝第二個和第三個物品可以使得背包恰好裝滿且總價值最大。

示例2

輸入

3 8
12 6
11 8
6 8

輸出

8
0

說明

裝第三個物品時總價值最大但是不滿，裝滿背包無解。

備注:

要求O(nV)的時間復雜度，O(V)空間復雜度

題目描述

給定 n 個物品，每個物品有體積 v[i] 和價值 m[i]。一個容量為 vs 的背包。

你可以選擇一些物品放入背包中，使得總體積 不超過或恰好等于 背包容量，目標是使總價值最大。

一、 DP 狀態定義

dp[i][j] 表示前 i 個物品中選擇若干物品，裝入容量為 j 的背包中可以獲得的最大價值。

這個狀態定義允許容量 j 不超過 當前背包容量，不要求填滿。

---

二、狀態轉移方程

對于每個物品 i 和容量 j：

• 如果當前物品可以放進容量 j 的背包中（即 j >= v[i]），那么有兩種選擇：
  • 不選這個物品：dp[i][j] = dp[i-1][j]
  • 選這個物品：dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + m[i])

否則：

• 只能不選：dp[i][j] = dp[i-1][j]

---

三、初始化方式

vector<vector<ll>> dp(n+1, vector<ll>(vs+1, INT_MIN));
dp[0][0] = 0;

• 初始狀態只有 dp[0][0] = 0，表示沒有物品、容量為 0 時合法；
• 其他所有狀態初始化為 INT_MIN（極小值），表示不可達；
• 這樣在后續轉移過程中，只保留有效路徑的狀態。

---

四、輸出策略

? 不要求填滿的情況下的最大價值（ender1）：

ll ender1 = INT_MIN;
for (ll i = vs; i >= 1; i--) {ender1 = max(ender1, dp[n][i]);
}
ender1 = (ender1 < 0) ? 0 : ender1;

• 遍歷 dp[n][1...vs]，找出最大值；
• 如果所有值都為負數，則說明沒有任何合法組合，返回 0。

? 必須恰好填滿容量 vs 的情況（ender2）：

ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];

• 直接取 dp[n][vs]；
• 如果它是負數，說明無法恰好填滿容量 vs，返回 0。

---

五、易錯點總結

易錯點	原因	解決方法
? 忽略 j=0 的遍歷	容量 j=0 是合法狀態，必須包含在內	內層循環從 j=0 開始
? 初始化錯誤	若將 dp 初始化為 0，會導致無法區分是否可達	使用 INT_MIN 表示不可達
? 忘記處理負值	若最終結果為負，說明無合法組合	加上 (val < 0) ? 0 : val 處理
? 不理解 ender1 和 ender2 區別	一個是“任意容量下”的最大值，一個是“特定容量”下的最大值	分開處理即可

---

六、完整代碼

#include<bits/stdc++.h>
using ll = long long;
using namespace std;int main()
{ll n, vs;cin >> n >> vs;vector<ll> m(n + 1, 0);vector<ll> v(n + 1, 0);for (ll i = 1; i <= n; ++i)cin >> v[i] >> m[i];// 初始化 dp 數組vector<vector<ll>> dp(n + 1, vector<ll>(vs + 1, INT_MIN));dp[0][0] = 0;for (ll i = 1; i <= n; i++) {for (ll j = 0; j <= vs; j++) {if (j >= v[i])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + m[i]);elsedp[i][j] = dp[i - 1][j];}}// 不要求填滿的最大價值ll ender1 = INT_MIN;for (ll i = vs; i >= 1; i--){ender1 = max(ender1, dp[n][i]);}ender1 = (ender1 < 0) ? 0 : ender1;// 恰好填滿的最大價值ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];cout << ender1 << endl << ender2;return 0;
}

---

想從（1,1）開始轉移的話

必須顯式初始化dp[n][0]=0;
代碼如下：

#include<bits/stdc++.h>
using ll = long long;
using namespace std;int main()
{ll n, vs;cin >> n >> vs;vector<ll>m(n + 1, 0);vector<ll>v(n + 1, 0);for (ll i = 1; i <= n; i++){cin >> v[i] >> m[i];}//原問題：這個背包至多能裝多大價值的物品//抽象成 前n個物品（經過選擇）裝滿體積為vs的背包 能獲得的最大價值//dp[i][j]表示 前i個物品（經過選擇）裝滿體積為vs的背包,能獲得的最大價值//狀態轉移方程：(每個位置的元素都有選 或 不選 兩種狀態)//dp[i][j]=max(dp[i-1][j](不選), dp[i-1][j-v[i]]+m[i])(選)//注意體積問題：體積j>=v[i]時，才能選擇當前物品vector<vector<ll>>dp(n + 1, vector<ll>(vs + 1, INT_MIN));//顯式初始化 前n件物品 （經過選擇） 裝滿體積為0的背包，能獲得的最大價值為0for (ll i = 0; i <= n; i++){dp[i][0] = 0;}for (ll i = 1; i <= n; i++){for (ll j = 1; j <= vs; j++){if (j >= v[i]){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + m[i]);}else{dp[i][j] = dp[i - 1][j];}}}//最大價值應該是最后一行：前n個物品 放滿 體積為j的最大價值（找最大的）//dp[n][vs]應該是填滿體積為vs時 創造的最大價值ll ender1 = INT_MIN;for (ll i = vs; i >= 1; i--){ender1 = max(ender1, dp[n][i]);}ender1 = (ender1 < 0) ? 0 : ender1;ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];//cout<<dp[n][vs]<<endl;cout << ender1 << endl << ender2;return 0;
}