目錄

最常見的0-1背包問題：

第一步：思考每輪的決策，定義狀態，從而得到dp表

第二步：找出最優子結構，進而推導出狀態轉移方程

第三步：確定邊界條件和狀態轉移順序

方法一：暴力搜素

代碼示例：

方法二：記憶化搜索

時間復雜度取決于子問題數量,也就是O（n*cap）。

實現代碼如下：

方法三：動態規劃

代碼如下所示：

方法四：空間優化

代碼示例

最常見的0-1背包問題：

Question:給定n個物品，第i個物品的重量為wgt[i]、價值為val[i]，和一個容量為cap的背包。每個物品只能選擇一次，問在限定背包的容量下能放入物品的最大價值。

觀察圖下所示，由于物品編號i從1開始計數，數組索引從0開始計數，因此物品i對應重量wgt[i]和價值val[i]。

我們可以將0-1背包問題看作一個由n輪決策組成的過程，對于每個物體都有不放入和放入兩種決策，因此該問題滿足決策樹模型。

該問題的目標是求解“在限定背包容量下能放入物品的最大價值”，因此較大概率是一個動態規劃的問題。

第一步：思考每輪的決策，定義狀態，從而得到dp表

對于每個物品來說，不放入背包，背包容量不變；放入背包，背包容量減小。由此可得狀態定義：當前物品編號i和剩余背包容量c，記作[i，c]。

狀態[i，c]對應的子問題為：前i個物品在剩余容量為c的背包中的最大價值，記為dp[i，c]。

待求解的是dp[n,cap]，因此需要一個尺寸為(n+1) * (cap+1)的二維dp表。

第二步：找出最優子結構，進而推導出狀態轉移方程

當我們做出物品i的決策后，剩余的是前i-1個物品的決策，可分為以下兩種情況。

1. 不放入物品i：背包容量不變，狀態變化為[i-1，c].
2. 放入物品i：背包容量減少wgt[i-1]，價值增加val[i-1]，狀態變化為[i-1,c-wgt[i-1]]。

上述分析揭示了本題的最優子結構：最大價值dp[I,c]等于不放入物品i和放入物品i兩種方案中價值更大的那一個。由此可以推導出狀態轉移方程為：

dp[i，c] = max(dp[i-1，c]，dp[i-1，c-wgt[i-1] ] + val[i-1])

需要注意是，當前物品重量wgt[i-1]超過剩余背包容量c，則只能選擇不放入背包。

第三步：確定邊界條件和狀態轉移順序

當無物品時或無背包剩余容量時最大價值為0，即首列dp[i，0]和首列dp[0,c]都等于0.

當前狀態[i，c]從上方的狀態[i-1,c]和左上方的狀態[i-1,c-wgt[i-1]]轉移而來，因此通過兩層循環正序遍歷整個dp表即可。

根據以上的分析，采取三種方法順序進行實現暴力搜索，記憶化搜索，動態規劃解法。

方法一：暴力搜素

搜索代碼需要包含的要素：

1. 遞歸參數：狀態[i，c]
2. 返回值：子問題的解dp[i，c]
3. 終止條件：當物品編號越界I = 0 或背包容量為0時，終止遞歸并返回價值0.
4. 剪枝：當前物品重量超出背包剩余容量時，則只能選擇不放入背包。

代碼示例：

# python 代碼示例def knapsack_dfs(wgt, val, i, c) :if i == 0 or c == 0 :return 0if wgt[i - 1] > c :return knapsack(wgt, val, i - 1, c)nohave = knapsack_dfs(wgt, val, i - 1, c)have = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]return max(nohave, have)

// C++代碼示例int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) :if (i == 0 || c == 0){return 0 ;}if (wgt[i - 1] > c){return knapsackDFS(wgt, val, i - 1, c) ;}int nohave = knapsackDFS(wgt, val, i - 1, c) ;int have = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1] ;return max(nohave, have) ;

如圖所示：由于每個物品都會產生選或者不選兩條搜索分支，因此時間復雜度為O（2^n）。

觀察遞歸樹，容易發現其中存在重疊子問題，例如dp[1,10]。而當物品較多，背包容量較大，尤其是相同重量的物品較多時，重疊子問題的數量將會大幅度增多。

方法二：記憶化搜索

為了保證重疊子問題只被計算一次，我們借助記憶列表mem來記錄子問題的解，其中menm[i][c]對應dp[i][c]。

時間復雜度取決于子問題數量,也就是O（n*cap）。

實現代碼如下：

# python 代碼示例
def knapsack_dfs_mem(wgt, val, i, c, mem) :if i == 0 or c == 0 :return 0if mem[i][c] != -1 :return mem[i][c]if wgt[i - 1] > c :return knapsack_dfs_mem(wgt, val, i - 1, c, mem)noput = knapsack_dfs_mem(wgt, val, i - 1, c, mem)yesput = knapsack_dfs_mem(wgt, val, i - 1, c - wgt[i - 1], mem) + val[i - 1]mem[i][c] = max(noput, yesput)return mem[i][c]

// c++ 代碼示例
int knapSackDFSMem(vector<int> &wgt, vector<int> &val, int i, int c, vector<int> &mem)
{if (i == 0 || c == 0){return 0 ;}if (mem[i][c] != 0){return mem[i][c] ;}if (wgt[i - 1] > c){return knapSackDFSMem(wgt, val, i - 1, c, mem) ;}int noput = knapSackDFSMem(wgt, val, i - 1, c, mem) ;int yesput = knapSackDFSMem(wgt, val, i - 1, c - wgt[i - 1], mem) + val[i - 1];mem[i][c] = max(noput, yesput) ;return mem[i][c] ;
}

方法三：動態規劃

動態規劃實質是就是在狀態轉移的過程中填充dp表的過程，

代碼如下所示：

# python 代碼示例
def knapsack_dp(wgt, val, cap) :n = len(wgt)dp = [ [0] * (cap + 1) for _ in range(n + 1)]for i in range(1, n + 1) :for c in range(1, cap + 1) :if wgt[i - 1] > c :dp[i][c] = dp[i - 1][c]else :dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) return dp[n][cap] 

// c++ 代碼示例
int knapSackDP(vector<int> &wgt, vector<int> &val, int cap)
{ int n = wgt.size() ;vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0)) ;for (int i = 1 ; i <= n ; i++){for (int c = 1 ; c <= cap ; c++){if (wgt[i - 1] > c){dp[i][c] = dp[i - 1][c] ;}else{dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])  ;}}}return dp[n][cap] ;
}

時間復雜度和空間復雜度都是由數組dp所決定的，即O（n*cap）。

如圖所示：

方法四：空間優化

由于每個狀態都至于其上一行有關系，因此我們可以使用兩個數組進行滾動前進，將復雜度從O（n^2）降低為O（n）。

進一步思考，我們能否僅用一個數組實現空間優化？觀察可知，每個狀態都是有正上方或左上方的格子的狀態轉移而來。假設只有一個數組，當開始遍歷第i行時，該數組存儲仍然是第i-1行的狀態。

1. 如果采取正序遍歷，那么遍歷到dp[i,j]時，左上方的dp[i-1,1]~dp[i-1,j-1]值可能已經覆蓋了，因此無法得到狀態轉移的正確結果。
2. 如果采取倒序遍歷，則不會發生覆蓋問題，狀態轉移可以正確的進行。

代碼示例：

def knap_sack_dp_comp(wgt, val, cap) :n = len(wgt)dp = [0] * (cap + 1)for i in range(1, n + 1) :for c in range(cap, 0 ,-1) :if wgt[i - 1] > c :dp[c] = dp[c]else :dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])return dp[cap]    

// c++ 代碼示例
int kanpSackDPComp(vector<int> &wgt, vector<int> &val, int cap)
{int n = wgt.size() ;vector<int> dp(cap + 1, 0) ;for (int i = 1 ; i <= n ; i++){for (int c = cap; c > 0 ; c--){if (wgt[i - 1] > c){dp[c] = dp[c] ;}else{dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) ;}}}return dp[cap] ;
}