本文介紹了背包問題系列，主要包括：

【1】 01-背包及其應(yīng)用
【2】完全背包及其應(yīng)用
【3】多重背包

【1】01-背包及其應(yīng)用：

1.1、01-背包問題描述：

有 N 件物品和一個(gè)容量為 C 的背包。第 i 件物品的重量是 w[i]，價(jià)值是 v[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價(jià)值總和最大。如：

其中 N = 4，C = 8， 則最大價(jià)值為 10（即把物品 2 和 4 放入背包）。

1.2、01-背包解題思路：

01-背包問題適合用動(dòng)態(tài)規(guī)劃求解，用 dp[i][j] 表示前 i 個(gè)物品放入容量為 j 的背包中的最大價(jià)值，因此此問題變成一個(gè)填表問題。如上述例子，dp[4][8] 就是最后的答案。

關(guān)鍵是找到狀態(tài)轉(zhuǎn)移方程。假設(shè)現(xiàn)在要計(jì)算 dp[i][j]，那么分為兩種情況：

• 如果當(dāng)前容量 j 小于第 i 件物品的重量（j < w[i]），則說(shuō)明第 i 件物品肯定無(wú)法放入背包，那么此背包還是只有前 i-1 個(gè)物品，即 dp[i][j] = dp[i-1][j]。
• 如果當(dāng)前容量 j 大于等于第 i 件物品的重量（j ≥ w[i]），則說(shuō)明第 i 件物品有放入背包的基本條件。那么到底能不能放要取決于第 i 件物品的加入能否使得總價(jià)值最大。如果不能最大化總價(jià)值，那么還是 dp[i][j] = dp[i-1][j]，表示不放入第 i 件物品；如果可以最大化總價(jià)值，那么 dp[i][j] = dp[i-1][j-w[i]] + v[i]，這里的 dp[i-1][j-w[i]] 為裝入第 i 件物品之前的狀態(tài)。

1.3、01-背包Python3 實(shí)現(xiàn)：

class Solution:
    def knapsack01(self, N, w, v, C):
        '''
        @param N: int, 物品總數(shù)
        @param w: List, 物品重量
        @param v: List, 物品價(jià)值
        @param C: int, 背包容量
        '''
        dp = [[0] * (C+1) for _ in range(N+1)]
        for i in range(1, N+1):
            for j in range(1, C+1):
                if j < w[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        return dp[-1][-1]

N = 4
w = [2,3,4,5]
v = [3,4,5,6]
C = 8
print(Solution().knapsack01(N, w, v, C))  # 10

注意：如果 j < w[i-1]，更新 dp[i][j] = dp[i-1][j] 是有必要的，比如下面的 dp[3][6] 的更新，就要用到 dp[2][2] 的結(jié)果。而 dp[2][2] 就是在 j < w[i-1] 的情況下使用 dp[2][2] = dp[1][2] 得到的：

之所以要強(qiáng)調(diào)這個(gè)點(diǎn)，是看到網(wǎng)上有人寫代碼直接寫成如下形式：

for i in range(1, N + 1):
    for j in range(w[i-1], C+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

這種直接省略了 j < w[i-1] 的情況。這是錯(cuò)誤的?。?！

1.4、01-背包空間優(yōu)化：

更進(jìn)一步發(fā)現(xiàn)，每一次 dp[i][j] 的改變只與 dp[i-1][x] { x : 1...j } 有關(guān)，dp[i-1][x] 是上一次循環(huán)保存下來(lái)的值；

因此，可以將 dp 縮成一維數(shù)組 dp[C+1]，從而達(dá)到優(yōu)化空間的目的，狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)換為：
dp[j] = max(dp[j], dp[j-w[i]] + v[i])。

注意：之前是二維數(shù)組，dp[i][j] 的更新依賴于 dp[i-1][x] 的結(jié)果。但是變成了一維數(shù)組后，對(duì)于一件物品 i，如果內(nèi)層循環(huán) j 仍然從小到大遍歷，剛剛更新的值在往后遍歷時(shí)又會(huì)被重新覆蓋，導(dǎo)致錯(cuò)誤的答案。

舉例（如果內(nèi)存循環(huán)從小到大遍歷）：

解決這種覆蓋問題的方法就是：內(nèi)存循環(huán)從大到小遍歷，這樣就不會(huì)出現(xiàn)覆蓋值的情況。這樣的話，物品 i 的所有更新就是依賴于 i-1 輪的結(jié)果，而不像從 j 小到大遍歷那樣對(duì)當(dāng)前更新的結(jié)果可能又重新覆蓋。

同時(shí)，因?yàn)閮?nèi)層循環(huán) j 從大到小遍歷了，所以只需要從容量 C 遍歷到 w[i-1] 即可。因?yàn)閷?duì)于 j < w[i-1]，一維數(shù)組 dp 中已經(jīng)有了，即就是二維數(shù)組下 dp[i-1][j] 的結(jié)果。所以對(duì)于 j < w[i-1] 的情況，不用更新即可。

空間優(yōu)化的代碼如下：

dp = [0] * (C+1)
for i in range(1, N+1):
    for j in range(C, w[i-1]-1, -1):   # j 從 C 開始從大到小遞減到 w[i-1]
        dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1])
return dp[-1]

這樣，時(shí)間復(fù)雜度雖然還是 O(n^2)，但是空間復(fù)雜度從 O(n^2) 變成了 O(n)。

1.5、與01-背包相關(guān)的Leetcode題目：

【416】判斷一個(gè)數(shù)組是否可以劃分成兩個(gè)相等的子集和

【2】完全背包及其應(yīng)用

2.1、完全背包問題描述：

有 N 種物品和一個(gè)容量是 C 的背包，每種物品都有無(wú)限件可用。第 i 種物品的重量是 wi，價(jià)值是 vi。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。輸出最大價(jià)值。

如01-背包中的例子，最大價(jià)值是 12，即可以在容量為 8 的背包中裝入 4 件物品 1，總價(jià)值 4 * 3 = 12。

2.2、完全背包解題思路：

與01-背包不同的是，完全背包問題是指每種物品都有無(wú)限個(gè)。但是，完全背包問題的解答幾乎與01-背包的一維數(shù)組解答一模一樣，唯一的區(qū)別是內(nèi)層循環(huán) j 的遍歷次序是遞增的，即 j 從 w[i-1] 到 C。

為什么？

• 在01-背包中，dp 依賴的是 i-1 輪的結(jié)果。但是完全背包問題中，dp 依賴的未必是 i-1 輪的狀態(tài)，而是同一輪中較小的 j。比如 C = 8，重量為 2 的物品在一輪更新時(shí)可以裝很多次。
• 01-背包中，要驗(yàn)證當(dāng)前第 i 個(gè)物品是否拿還是不拿必須依賴 i-1輪的狀態(tài)，絕對(duì)不會(huì)出現(xiàn)已經(jīng)拿取了第 i 個(gè)物品的情況。但是在完全背包中，由于物品有多個(gè)，可能要驗(yàn)證當(dāng)前是否已經(jīng)取過若干個(gè)第 i 個(gè)物品了。
• 所以內(nèi)層循環(huán) j 的遍歷是由小到大遞增的。

其實(shí)很簡(jiǎn)單地可以理解為：有一個(gè)一維數(shù)組 dp[C+1]，對(duì)于每件物品，盡可能多的裝進(jìn)去，不斷地用最大價(jià)值去刷新這個(gè)數(shù)組。最后，得到的 dp[-1] 就是最后的答案。

2.3、Python3 實(shí)現(xiàn)：

class Solution:
    def knapsack01(self, N, w, v, C):
        '''
        @param N: int, 物品總數(shù)
        @param w: List, 物品重量
        @param v: List, 物品價(jià)值
        @param C: int, 背包容量
        '''
        dp = [0] * (C+1)
        for i in range(1, N+1):
            for j in range(w[i-1], C+1):   # j 從 w[i-1] 開始從小到大遞增到 C
                dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1])
        return dp[-1]

N = 4
w = [2,3,4,5]
v = [3,4,5,6]
C = 8
print(Solution().knapsack01(N, w, v, C))  # 12

2.4、與完全背包相關(guān)的Leetcode題目：

【322】找硬幣問題，求需要的最少硬幣數(shù)

【3】多重背包

多重背包問題限定了一種物品的個(gè)數(shù)。解決多重背包問題，只需要把它轉(zhuǎn)化為01-背包問題即可。

比如，有 2 件價(jià)值為 5，重量為 2 的同一物品，我們就可以分為物品 a 和物品 b，a 和 b 的價(jià)值都為 5，重量都為 2，但我們把它們視作不同的物品。

之后，做法與01-背包相同。代碼參考01-背包代碼即可。