關(guān)于01背包問題，你該了解這些!

這周我們正式開始講解背包問題!

但說實(shí)話，背包九講對于小白來說確實(shí)不太友好，看起來還是有點(diǎn)費(fèi)勁的，而且都是偽代碼理解起來也吃力。

對于面試的話，其實(shí)掌握01背包，和完全背包，就夠用了，最多可以再來一個多重背包。

如果這幾種背包，分不清，我這里畫了一個圖，如下：

分割等和子集1

至于背包九講中其他背包，面試幾乎不會問，都是競賽級別的了，leetcode上連多重背包的題目都沒有，所以題庫也告訴我們，01背包和完全背包就夠用了。

而完全背包又是也是01背包稍作變化而來，即：完全背包的物品數(shù)量是無限的。

所以背包問題的理論基礎(chǔ)重中之重是01背包，一定要理解透!

leetcode上沒有純01背包的問題，都是01背包應(yīng)用方面的題目，也就是需要轉(zhuǎn)化為01背包問題。

所以我先通過純01背包問題，把01背包原理講清楚，后續(xù)再講解leetcode題目的時候，重點(diǎn)就是講解如何轉(zhuǎn)化為01背包問題了。

之前可能有些錄友已經(jīng)可以熟練寫出背包了，但只要把這個文章仔細(xì)看完，相信你會意外收獲!

01 背包

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

動態(tài)規(guī)劃-背包問題

這是標(biāo)準(zhǔn)的背包問題，以至于很多同學(xué)看了這個自然就會想到背包，甚至都不知道暴力的解法應(yīng)該怎么解了。

這樣其實(shí)是沒有從底向上去思考，而是習(xí)慣性想到了背包，那么暴力的解法應(yīng)該是怎么樣的呢?

每一件物品其實(shí)只有兩個狀態(tài)，取或者不取，所以可以使用回溯法搜索出所有的情況，那么時間復(fù)雜度就是，這里的n表示物品數(shù)量。

所以暴力的解法是指數(shù)級別的時間復(fù)雜度。進(jìn)而才需要動態(tài)規(guī)劃的解法來進(jìn)行優(yōu)化!

在下面的講解中，我舉一個例子：

背包最大重量為4。

物品為：

問背包能背的物品最大價(jià)值是多少?

以下講解和圖示中出現(xiàn)的數(shù)字都是以這個例子為例。

二維dp數(shù)組01背包

依然動規(guī)五部曲分析一波。

確定dp數(shù)組以及下標(biāo)的含義

對于背包問題，有一種寫法， 是使用二維數(shù)組，即dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。

只看這個二維數(shù)組的定義，大家一定會有點(diǎn)懵，看下面這個圖：

動態(tài)規(guī)劃-背包問題1

要時刻記著這個dp數(shù)組的含義，下面的一些步驟都圍繞這dp數(shù)組的含義進(jìn)行的，如果哪里看懵了，就來回顧一下i代表什么，j又代表什么。

確定遞推公式

再回顧一下dp[i][j]的含義：從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。

那么可以有兩個方向推出來dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時，物品i無法放進(jìn)背包中，所以被背包內(nèi)的價(jià)值依然和前面相同。)
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價(jià)值，那么dp[i - 1][j - weight[i]] + value[i] (物品i的價(jià)值)，就是背包放物品i得到的最大價(jià)值

所以遞歸公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp數(shù)組如何初始化

關(guān)于初始化，一定要和dp數(shù)組的定義吻合，否則到遞推公式的時候就會越來越亂。

首先從dp[i][j]的定義出發(fā)，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價(jià)值總和一定為0。如圖：

動態(tài)規(guī)劃-背包問題2

在看其他情況。

狀態(tài)轉(zhuǎn)移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推導(dǎo)出來，那么i為0的時候就一定要初始化。

dp[0][j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價(jià)值。

那么很明顯當(dāng) j < weight[0]的時候，dp[0][j] 應(yīng)該是 0，因?yàn)楸嘲萘勘染幪?的物品重量還小。

當(dāng)j >= weight[0]時，dp[0][j] 應(yīng)該是value[0]，因?yàn)楸嘲萘糠抛銐蚍啪幪?物品。

代碼初始化如下：

for (int j = 0 ; j < weight[0]; j++) {  // 當(dāng)然這一步，如果把dp數(shù)組預(yù)先初始化為0了，這一步就可以省略，但很多同學(xué)應(yīng)該沒有想清楚這一點(diǎn)。 
    dp[0][j] = 0; 
} 
// 正序遍歷 
for (int j = weight[0]; j <= bagweight; j++) { 
    dp[0][j] = value[0]; 
} 

此時dp數(shù)組初始化情況如圖所示：

動態(tài)規(guī)劃-背包問題7

dp[0][j] 和 dp[i][0] 都已經(jīng)初始化了，那么其他下標(biāo)應(yīng)該初始化多少呢?

其實(shí)從遞歸公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方數(shù)值推導(dǎo)出來了，那么 其他下標(biāo)初始為什么數(shù)值都可以，因?yàn)槎紩桓采w。

初始-1，初始-2，初始100，都可以!

但只不過一開始就統(tǒng)一把dp數(shù)組統(tǒng)一初始為0，更方便一些。

如圖：

動態(tài)規(guī)劃-背包問題10

最后初始化代碼如下：

// 初始化 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]; 
} 

費(fèi)了這么大的功夫，才把如何初始化講清楚，相信不少同學(xué)平時初始化dp數(shù)組是憑感覺來的，但有時候感覺是不靠譜的。

確定遍歷順序

在如下圖中，可以看出，有兩個遍歷的維度：物品與背包重量

動態(tài)規(guī)劃-背包問題3

那么問題來了，先遍歷 物品還是先遍歷背包重量呢?

其實(shí)都可以!!但是先遍歷物品更好理解。

那么我先給出先遍歷物品，然后遍歷背包重量的代碼。

// weight數(shù)組的大小 就是物品個數(shù) 
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]); 
 
    } 
} 

先遍歷背包，再遍歷物品，也是可以的!(注意我這里使用的二維dp數(shù)組)

例如這樣：

// weight數(shù)組的大小 就是物品個數(shù) 
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量 
    for(int i = 1; i < weight.size(); i++) { // 遍歷物品 
        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]); 
    } 
} 

為什么也是可以的呢?

要理解遞歸的本質(zhì)和遞推的方向。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 遞歸公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推導(dǎo)出來的。

dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正上方向)，那么先遍歷物品，再遍歷背包的過程如圖所示：

動態(tài)規(guī)劃-背包問題5

再來看看先遍歷背包，再遍歷物品呢，如圖：

動態(tài)規(guī)劃-背包問題6

大家可以看出，雖然兩個for循環(huán)遍歷的次序不同，但是dp[i][j]所需要的數(shù)據(jù)就是左上角，根本不影響dp[i][j]公式的推導(dǎo)!

但先遍歷物品再遍歷背包這個順序更好理解。

其實(shí)背包問題里，兩個for循環(huán)的先后循序是非常有講究的，理解遍歷順序其實(shí)比理解推導(dǎo)公式難多了。

舉例推導(dǎo)dp數(shù)組

來看一下對應(yīng)的dp數(shù)組的數(shù)值，如圖：

動態(tài)規(guī)劃-背包問題4

最終結(jié)果就是dp[2][4]。

建議大家此時自己在紙上推導(dǎo)一遍，看看dp數(shù)組里每一個數(shù)值是不是這樣的。

做動態(tài)規(guī)劃的題目，最好的過程就是自己在紙上舉一個例子把對應(yīng)的dp數(shù)組的數(shù)值推導(dǎo)一下，然后在動手寫代碼!

很多同學(xué)做dp題目，遇到各種問題，然后憑感覺東改改西改改，怎么改都不對，或者稀里糊涂就改過了。

主要就是自己沒有動手推導(dǎo)一下dp數(shù)組的演變過程，如果推導(dǎo)明白了，代碼寫出來就算有問題，只要把dp數(shù)組打印出來，對比一下和自己推導(dǎo)的有什么差異，很快就可以發(fā)現(xiàn)問題了。

完整c++測試代碼

void test_2_wei_bag_problem1() { 
    vector<int> weight = {1, 3, 4}; 
    vector<int> value = {15, 20, 30}; 
    int bagweight = 4; 
 
    // 二維數(shù)組 
    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數(shù)組的大小 就是物品個數(shù) 
    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(); 
} 

總結(jié)

講了這么多才剛剛把二維dp的01背包講完，這里大家其實(shí)可以發(fā)現(xiàn)最簡單的是推導(dǎo)公式了，推導(dǎo)公式估計(jì)看一遍就記下來了，但難就難在如何初始化和遍歷順序上。

可能有的同學(xué)并沒有注意到初始化 和 遍歷順序的重要性，我們后面做力扣上背包面試題目的時候，大家就會感受出來了。

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。