01背包問題基礎
問題描述
有n件物品和一個最多能背重量為
w
的背包。第
i
件物品的重量是
weight[i]
，得到的價值是
value[i]
。每件物品隻能用一次，求解将哪些物品裝入背包裡物品價值總和最大。
舉個栗子
背包最大重量為4。
物品為：
| 重量 | 價值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
二維dp數組01背包
動歸五部曲
1.确定dp數組以及下标的含義
對于背包問題，有一種寫法， 是使用二維數組，即
dp[i][j]
表示從下标為
[0-i]
的物品裡任意取，放進容量為j的背包，價值總和最大是多少。
2.确定遞推公式
可以有兩個方向推出來
dp[i][j]
，
- 不放物品i：由
dp[i - 1][j]
dp[i][j]
dp[i - 1][j]
- 放物品i：由
dp[i - 1][j - weight[i]]
dp[i - 1][j - weight[i]]
j - weight[i]
dp[i - 1][j - weight[i]] + value[i]
是以遞歸公式：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
3.dp數組如何初始化
首先從dp[i][j]的定義出發，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價值總和一定為0。如圖：
其次是其他情況。狀态轉移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
; 可以看出i 是由
i-1
推導出來，那麼i為0的時候就一定要初始化。
dp[0][j]
，即：
i
為0，存放編号0的物品的時候，各個容量的背包所能存放的最大價值。
那麼很明顯當
j < weight[0]
的時候，
dp[0][j]
應該是 0，因為背包容量比編号0的物品重量還小。
當
j >= weight[0]
時，
dp[0][j]
應該是
value[0]
，因為背包容量放足夠放編号0物品。
代碼初始化如下：
for (int j = 0 ; j < weight[0]; j++) { // 當然這一步，如果把dp數組預先初始化為0了，這一步就可以省略，但很多同學應該沒有想清楚這一點。
dp[0][j] = 0;
}
// 正序周遊
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
此時dp數組初始化情況如圖所示：
dp[0][j]
和
dp[i][0]
都已經初始化了，那麼其他下标應該初始化多少呢？
其實從遞歸公式：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
; 可以看出
dp[i][j]
是由左上方數值推導出來了，那麼 其他下标初始為什麼數值都可以，因為都會被覆寫。
是以為了友善，可以初始化為0。
最後初始化代碼如下：
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
4.确定周遊順序
先周遊 物品還是先周遊背包重量呢？其實都可以，但是先周遊物品更好了解。
那麼我先給出先周遊物品，然後周遊背包重量的代碼。
// weight數組的大小 就是物品個數
for(int i = 1; i < weight.size(); i++) { // 周遊物品
for(int j = 0; j <= bagweight; j++) { // 周遊背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
5.舉例推導dp數組
對應的dp數組的數值，如圖：
void test_2_wei_bag_problem1() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagweight = 4;
// 二維數組
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
// weight數組的大小 就是物品個數
for(int i = 1; i < weight.size(); i++) { // 周遊物品
for(int j = 0; j <= bagweight; j++) { // 周遊背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout << dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
}
01背包問題之滾動數組（二維轉化成一維）
動規五部曲分析如下：
1.确定dp數組的定義
在一維dp數組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為
dp[j]
。
2.一維dp數組的遞推公式
dp[j]
為 容量為j的背包所背的最大價值，那麼如何推導dp[j]呢？
dp[j]
可以通過
dp[j - weight[i]]
推導出來，
dp[j - weight[i]]
表示容量為
j - weight[i]
的背包所背的最大價值。
dp[j - weight[i]] + value[i]
表示 容量為 j - 物品i重量 的背包 加上 物品i的價值。（也就是容量為j的背包，放入物品i了之後的價值即：dp[j]）
此時
dp[j]
有兩個選擇，一個是取自己
dp[j]
相當于 二維dp數組中的
dp[i-1][j]
，即不放物品
i
，一個是取
dp[j - weight[i]] + value[i]
，即放物品
i
，指定是取最大的，畢竟是求最大價值，
是以遞歸公式為：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
;
可以看出相對于二維dp數組的寫法，就是把
dp[i][j]
中i的次元去掉了。
3.一維dp數組如何初始化
dp[j]
表示：容量為j的背包，所背的物品價值可以最大為
dp[j]
，那麼dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。
那麼dp數組除了下标0的位置，初始為0，其他下标應該初始化多少呢？
看一下遞歸公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
;
dp數組在推導的時候一定是取價值最大的數，如果題目給的價值都是正整數那麼非0下标都初始化為0就可以了。
這樣才能讓dp數組在遞歸公式的過程中取的最大的價值，而不是被初始值覆寫了。
那麼我假設物品價值都是大于0的，是以dp數組初始化的時候，都初始為0就可以了。
4.一維dp數組周遊順序
代碼如下：
for(int i = 0; i < weight.size(); i++) { // 周遊物品
for(int j = bagWeight; j >= weight[i]; j--) { // 周遊背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
這裡大家發現和二維dp的寫法中，周遊背包的順序是不一樣的！
二維dp周遊的時候，背包容量是從小到大，而一維dp周遊的時候，背包是從大到小。
為什麼呢？
倒序周遊是為了保證物品i隻被放入一次！。但如果一旦正序周遊了，那麼物品0就會被重複加入多次！
舉一個例子：物品0的重量
weight[0] = 1
，價值
value[0] = 15
如果正序周遊
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此時
dp[2]
就已經是30了，意味着物品0，被放入了兩次，是以不能正序周遊。
為什麼倒序周遊，就可以保證物品隻放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp數組已經都初始化為0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
是以從後往前循環，每次取得狀态不會和之前取得狀态重合，這樣每種物品就隻取一次了。
那麼問題又來了，為什麼二維dp數組曆的時候不用倒序呢？
因為對于二維dp，
dp[i][j]
都是通過上一層即
dp[i - 1][j]
計算而來，本層的
dp[i][j]
并不會被覆寫！
再來看看兩個嵌套for循環的順序，代碼中是先周遊物品嵌套周遊背包容量，那可不可以先周遊背包容量嵌套周遊物品呢？
不可以！
因為一維dp的寫法，背包容量一定是要倒序周遊（原因上面已經講了），如果周遊背包容量放在上一層，那麼每個dp[j]就隻會放入一個物品，即：背包裡隻放入了一個物品。
倒序周遊的原因是，本質上還是一個對二維數組的周遊，并且右下角的值依賴上一層左上角的值，是以需要保證左邊的值仍然是上一層的，從右向左覆寫。
是以一維dp數組的背包在周遊順序上和二維其實是有很大差異的！，這一點大家一定要注意。
5.舉例推導dp數組
一維dp，分别用物品0，物品1，物品2 來周遊背包，最終得到結果如下：
void test_1_wei_bag_problem() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 周遊物品
for(int j = bagWeight; j >= weight[i]; j--) { // 周遊背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_1_wei_bag_problem();
}