前言

小M公司年會運(yùn)氣爆棚中獎凯旋，老板說給你一個容量w的蛇皮袋，去獎池里愉快的撈吧钉迷。獎池里的商品都獨一份至非。袋子能裝多少，就算中多少糠聪。不同獎品體積價格都不同荒椭，且每種獎品拿一次喔。小M心想這機(jī)會千載難逢舰蟆，我咋薅才能讓老板薅出血趣惠。

這個場景中如果歸納到算法中來說狸棍，都是很典型的背包問題。都可簡化為：
有N個物品信卡，這些物品有各自的體積W和價值V「糇海現(xiàn)有已定容量的背包，求如何讓背包里裝入的物品價值總和最大傍菇？

總結(jié).png

動態(tài)規(guī)劃的原理

動態(tài)規(guī)劃（Dynamic Programming）丢习，簡稱DP牵触。若某一問題有很多重疊子問題，往往使用動態(tài)規(guī)劃是最有效的咐低。動態(tài)規(guī)劃中每一個狀態(tài)都是由上一個狀態(tài)推導(dǎo)出來的揽思。對應(yīng)貪心是沒有狀態(tài)推導(dǎo)，而是從局部直接選最優(yōu)的见擦，分治法在子問題上會被重復(fù)計算多次钉汗。而DP有記憶性，計算過程中會被記錄下來鲤屡，在新問題里需要用到的子問題可以直接提取损痰，避免重復(fù)計算、節(jié)約了時間酒来。

最優(yōu)性原理是動態(tài)規(guī)劃的基礎(chǔ)卢未，最優(yōu)性原理是指“多階段決策過程的最優(yōu)決策序列具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言堰汉，其后各階段的決策序列必須構(gòu)成最優(yōu)策略”辽社。

動態(tài)規(guī)劃解題思路

1. 確定dp數(shù)組和其下標(biāo)的含義
2. 推導(dǎo)出狀態(tài)轉(zhuǎn)移方程
3. 初始化dp數(shù)組
4. 確定遍歷的順序

對于以上的前兩個步驟：
將問題抽象化、確定個模型 -> 尋找約束條件 -> 判斷是否滿足最優(yōu)性 -> 找大問題與小問題的關(guān)系

1. 確定dp數(shù)組和其下標(biāo)的含義

dp[i][j]表示從下標(biāo)為[0 - i]的物品里任意取翘鸭，放進(jìn)剩余容量為j的背包滴铅，價值總和最大值。

2. 推導(dǎo)狀態(tài)轉(zhuǎn)移方程

可區(qū)分為兩種情況來推出遞推公式：

1. 當(dāng)?shù)趇件物品太重放不進(jìn)去就乓，那么此時背包未放第i件物品失息，此時dp[i][j] = dp[i - 1][j]
2. 當(dāng)?shù)趇件物品重量小于剩余的背包大小，可以放入時档址。又區(qū)分為兩種情況盹兢。
   1. 放：dp[i][j] = dp[i - 1][j - w[j]] + v[i]
   2. 不放：dp[i][j] = dp[i - 1][j]
      此時對于放和不放，我們要選二者的較大值守伸。下面放一張log圖幫助理解绎秒。注意log的最后一行。
      
      image.png
      
      沒看懂尼摹？來见芹，再默念一遍dp[i][j]表示從下標(biāo)為[0 - i]的物品里任意取剂娄，放進(jìn)剩余容量為j的背包，價值總和最大值玄呛。

3. 初始化dp數(shù)組

背包剩余容量為0的時候阅懦，肯定是不可再放入東西。所以dp[i][0] = 0

vector<vector<int>> dp(wSize + 1, vector<int>(bagW + 1, 0));

接下來徘铝，根據(jù)上一步的出來的動態(tài)轉(zhuǎn)移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + v[i])可以知i是由i - 1推出來的耳胎，所以i為0的時候就一定要初始化。另外惕它，倒敘遍歷怕午，保證物品0只被放入一次。

for (int j = bagW; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

4. 確定遍歷的順序

填表.png

綜上兆蕉，上代碼

    vector<int> weight = {1, 3, 5};
    vector<int> value = {15, 20, 30};
    int bagW = 5;

    size_t wSize = weight.size();
    vector<vector<int>> dp(wSize + 1, vector<int>(bagW + 1, 0));

    for (int j = bagW; j >= weight[0]; j--) {
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }

    for(int i = 1; i < wSize; i++) {
        for(int j = 0; j <= bagW; 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]);
            }
        }
    }
    printf("max value = %d", dp[wSize - 1][bagW]);

優(yōu)化成一維數(shù)組

滾動數(shù)組：讓數(shù)組滾起來，很直白吧缤沦。這是一種用時間去換空間的思路虎韵。滾動數(shù)組基本上都是在DP和遞推中使用，大部分都是通過數(shù)組中的值結(jié)合其他的數(shù)更新數(shù)組中的某一位疚俱，之后在數(shù)組中交換數(shù)值的位置劝术，再更新下一位缩多。

上一步我們得出本題如果用二位數(shù)組呆奕，遞推公式為：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + v[i])
同時我們也知道動態(tài)規(guī)劃中每一個狀態(tài)都是由上一個狀態(tài)推導(dǎo)出來的。所以dp[i - 1]可以直接放入到dp[i]衬吆。所以可改為：
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + v[i])

上面的狀態(tài)轉(zhuǎn)移方程梁钾，記錄下了每次操作后的最大價值，但是最后需要的結(jié)果只有最后一行的最大容量的價值逊抡。根據(jù)上一行得到下行數(shù)據(jù)后姆泻，上一行的數(shù)據(jù)就是沒有用處的了。所以優(yōu)化空間冒嫡，用一個一維數(shù)組dp[j]拇勃。

1. 確定dp數(shù)組和其下標(biāo)的含義

在01背包問題中，dp[j]表示：容量為j的背包孝凌，所背的物品價值最大為dp[j]方咆。

2. 推導(dǎo)狀態(tài)轉(zhuǎn)移方程

dp[j]可由dp[j - weight[i]]推出，表示容量為j - weight[i]的背包所背的最大價值蟀架。
dp[j - weight[i]] + value[i]：容量為j的背包瓣赂，放入物品i了榆骚，減去weight[i]，加上對應(yīng)i的價值
依據(jù)題意取dp[j]與dp[j - weight[i]] + value[i]間較大值煌集。
所以遞歸公式為:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 初始化dp數(shù)組

因為背包容量為0妓肢，所背的物品的最大價值肯定也是0.

4. 確定遍歷的順序

舉個例子：物品0的weight[0] = 1，value[0] = 15

正序遍歷：
dp[1] = dp[1 - weight[0]] + value[0] => dp[1] = 15
dp[2] = dp[2 - weight[0]] + value[0] => dp[2] = 30
此時dp[2]就已經(jīng)是30了苫纤，物品0已經(jīng)被放入了兩次碉钠，所以不能正序遍歷。

倒序遍歷：
dp[2] = dp[2 - weight[0]] + value[0] => dp[2] = 15
dp[1] = dp[1 - weight[0]] + value[0] => dp[1] = 15
所以需要從后從后向前遍歷方面，每次取得狀態(tài)不會和之前取得狀態(tài)重合放钦，這樣每種物品就只取一次了。另外恭金，如果遍歷背包容量放在外層操禀，那么每個dp[j]只會放入一個物品横腿，即背包里只放入了一個物品颓屑。所以需要背包容量的遍歷要放在內(nèi)層。

    size_t wSize = weight.size();
    for (int i = 0; i < wSize; i++) {
        //遍歷背包容量
        for(int j = bagW; j >= weight[i]; j--) {

        } 
    }

綜上耿焊，上完整代碼

    vector<int> weight = {1, 3, 5};
    vector<int> value = {15, 20, 30};
    int bagW = 5;

    size_t wSize = weight.size();
    vector<int>(bagW + 1, 0);

    for(int i = 0; i < wSize; i++) {
        //遍歷背包容量
        for(int j = bagW; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    printf("max value = %d", dp[bagW]);

其他一些算法筆記

鳴謝

在此非常感謝代碼隨想錄的思路揪惦。在筆者之前刷leetcode dp和二叉樹類題目時，陈藓睿看到這位大佬的精妙解題器腋。在回顧背包問題時，本文也深受大佬的啟發(fā)钩杰。

其他算法詳細(xì)題解