【LeetCode動態規劃#05】揹包問題的理論分析（基於程式碼隨想錄的個人理解，多圖）

揹包問題

問題描述

揹包問題是一系列問題的統稱，具體包括：01揹包、完全揹包、多重揹包、分組揹包等（僅需掌握前兩種，後面的為競賽級題目）

下面來研究01揹包

實際上即使是最經典的01揹包，也不會直接出現在題目中，一般是融入到其他的題目背景中再考察

因為是學習原理，所以先跳過最原始的問題模板來學。

01揹包的原始題意是：（標準的揹包問題）

有n件物品和一個最多能背重量為 w 的揹包。第 i 件物品的重量是 weight[i] ，得到的價值是 value[i] 。每件物品只能用一次，求解將哪些物品裝入揹包裡物品價值總和最大。

（01揹包問題可以使用暴力解法，每一件物品其實只有兩個狀態，取或者不取，所以可以使用回溯法搜尋出所有的情況，那麼時間複雜度就是O(2^n)，這裡的n表示物品數量。因為暴力搜尋的時間複雜度是指數級別的，所以才需要通過dp來進行優化）

根據上面的描述可以舉出以下例子

二維dp陣列01揹包

揹包最大重量為4。

物品為：

	重量	價值
物品0	1	15
物品1	3	20
物品2	4	30

問揹包能背的物品最大價值是多少？

五部曲分析一波

五步走

1、確定dp陣列含義

該問題中的dp陣列應該是二維的，所以先定義一個dp[i][j]

該陣列的含義是什麼？

含義：任取編號（下標）為[0, i]之間的物品放進容量為j的揹包裡

假設有一個要求的元素dp[x][x]，根據前面對遞推公式的討論可知，該元素一定是由兩個方向推過來求得的。

也就是情況1、情況2，那麼對應到圖中就是從上到下推過來的，是情況1（dp[i - 1][j]）

情況2（dp[i - 1][j - weight[i]]）在圖中體現得不是十分確定，但是大致方向是從左上角往下推過來的

這兩個方向的源頭分別指向綠色區域和橙色區域

那麼這兩個區域就是要初始化的區域，怎麼初始化呢？

先說橙色區域，從dp[i][j]的定義出發，如果揹包容量j為0的話，即dp[i][0]，無論是選取哪些物品，揹包價值總和一定為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][j] = 0;
}
// 正序遍歷
for (int j = weight[0]; j <= bagweight; j++) {//綠色區域
    dp[0][j] = value[0];
}

以上兩個區域實際上屬於「含0下標區域」，其他的「非0下標區域」也需要初始化（沒想清楚為什麼有時要初始化完整個dp陣列，有時又不用）

「非0下標區域」初始化為任何值都可以

還是拿前面的圖來看

以dp[x][x]這個位置為例，其初始化成100、200都無所謂，因為這個位置的dp值是由其上面和左上兩個方向上的情況推匯出來的，只取決於這裡個方向最開始的初始化值。

（例如dp[x][x]這裡初始化為100，我從上面推導下來之後會用推導值將100覆蓋）

4、確定遍歷方式

該問題中dp陣列有兩個維度：物品、揹包容量，先遍歷哪個呢？

直接說結論，都行，但是先遍歷物品更好理解

（具體看程式碼隨想錄解釋）

兩種過程的圖如下：

（這裡需要重申一下揹包問題的條件：每個物品只能用一次，要求的是怎麼裝揹包裡的價值最大）

先遍歷物品再遍歷揹包容量（固定物品編號，遍歷揹包容量）

挑一個節點來說一下（圖中的紅框部分），此時的遍歷順序是先物後包，物品1(重3價20)在0~4種容量中放置的結果如圖所示

因為固定了物品1，此時揹包容量為0、1、2的情況都是放不下物品1的（又也放不下物品3），所以只能放物品0（此為最佳選擇）

當遍歷到揹包容量為3時，可以放下物品1了，那此處的最佳選擇就是放一個物品1，所以此處的dp陣列值變為20

其餘位置分析方法同理

先遍歷揹包容量再遍歷物品（固定揹包容量，遍歷物品編號）

有了前面的例子，這裡就很好理解了，就是從上往下遍歷，固定住當前揹包的容量，遍歷物品，看看能不能放入，能放的話最優選擇應該放哪個

還是拿紅框部分來說，此時揹包容量固定為3

第一次遍歷，物品0可以裝下，此時最優選擇就是放物品0，揹包總價是15；

第二次遍歷，物品1可以裝下，此時最優選擇就是放物品1，揹包總價是20；

第二次遍歷，物品2裝不下，此時最優選擇就是放物品1，揹包總價還是20；

其餘位置分析方法同理

完整c++測試程式碼（卡哥）

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();
}