提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

文章目錄

• 一、01背包問題理論基礎（一）
• • 動態規劃五部曲
  • • 確定dp數組以及下標的含義
    • 確定遞推公式
    • 初始化dp數組
    • 確定遍歷順序
• 二、01背包問題理論基礎（二）
• • 動態規劃五部曲
  • • 確定dp數組以及下標的含義
    • 確定遞推公式
    • 初始化dp數組
    • 確定遍歷順序
    • 代碼
• 三、Leetcode 416. 分割等和子集
• • 動態規劃五部曲
  • • 確定dp數組以及下標的含義
    • 確定遞推公式
    • 初始化dp數組
    • 確定遍歷順序
  • 代碼

---

一、01背包問題理論基礎（一）

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

動態規劃五部曲

確定dp數組以及下標的含義

這里我們使用二維數組 dp[i][j]。其中 i 代表物品，j 代表背包。

dp 數組表示的含義是，當背包重量為 j 時，我們從 0 到 i 個物品中進行取舍，能獲得的最大價值。

本題中 dp 數組的定義十分關鍵！

確定遞推公式

當我們背包重量為 i 的時候，我們一共有兩種情況。

• 背包重量小于物品 i 的重量時，我們無法放入物品，所以我們直接繼承上一個狀態 dp[i-1][j] ，也就是當背包重量為 j 時，我們從 0 到 i-1 個物品中進行取舍，能獲得的最大價值。
• 當背包重量大于物品 i 的重量時，我們有兩種選擇，考慮是否選擇將物品 i 放入背包內。

1. 不將物品 i 放入背包內，此時我們也是繼承上一個狀態 dp[i-1][j]。
2. 將物品 i 放入背包內，此時的狀態應為：當前背包容量減去物品 i 的重量在 0 到 i-1 個物品中任意取的最大值再加上物品 i 的價值。，即 dp[i][j] = dp[i - 1][j - weight[i]] + value[i]

我們的目的是獲得最大的價值，所以當背包重量大于物品 i 的重量時，我們對兩種情況取最大值 max(dp[i - 1][j - weight[i]] + value[i], dp[i-1][j])。

最后得出遞推公式：

if weight[i-1] > j:dp[i][j] = dp[i-1][j]
else:dp[i][j] = max[dp[i - 1][j - weight[i]] + value[i], dp[i-1][j]]

初始化dp數組

將二維數組理解成為一個表格，行代表物品，列代表背包重量。

我們當前要計算的表格是通過左上方的表格遞推出來的，所以我們要對第一列和第一行進行初始化。

第一行代表的是，當背包重量為 j 時，對第一個物品進行取舍，我們能得到的最大價值。
這時我們只有一個物品可以考慮，所以向右遍歷，當物品的重量大于等于背包重量時，表示這個物品可以放進背包內，這時右面的表格就初始化為第一個物品的價值。左面的表格就初始化為 0。

第一列代表的是，當背包重量為 0 時，對前 i 個物品進行取舍能獲得的最大價值。背包重量是 0，當然什么物品也放不進去，所以第一列全部初始化為 0。

其余位置都是通過遞推公式計算得出，所以初始值無所謂，全部初始化為 0。

確定遍歷順序

很顯然，我們需要兩層 for 循環，那么到底是先遍歷物品還是先遍歷背包呢？

本題中先遍歷背包和先遍歷物品都可以！

• 先遍歷物品的方式更符合動態規劃的自底向上的求解思路。先考慮只有一個物品時，對于不同背包容量的最大價值，然后逐步增加物品數量，計算在當前物品加入的情況下，不同背包容量的最大價值。這種方式可以清晰地看到狀態是如何逐步轉移和構建的
• 先遍歷背包的方式則是先固定背包容量，然后看在這個容量下，不同物品組合能達到的最大價值。雖然代碼執行順序不同，但最終也能正確計算出所有狀態的最大價值。

代碼：

n, bagweight = map(int, input().split())weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [[0] * (bagweight + 1) for _ in range(n)]for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]for i in range(1, n):for j in range(bagweight + 1):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])print(dp[n - 1][bagweight])

二、01背包問題理論基礎（二）

對于遞歸問題，有的時候我們當前狀態只是通過前面幾個狀態進行推導，如果定義一個很長的數組，那么大部分的空間是被浪費的，滾動數組就是在空間上進行優化的一種方法。

舉一個例子，斐波那契數列問題。我們的狀態轉移方程是 dp[i]=dp[i-1]+dp[i-2 。那么當前狀態是由前兩個狀態推導而來，當我們推導 dp[3] 的時候，dp[0] 就已經用不到了，所以我們完全可以將推導得到的 dp[3] 放在 dp[0] 的位置，這樣我們只開辟了三塊空間就能完成整個計算，大大節省了空間，這就是滾動數組的思想。

對于 01 背包問題，我們當前層的狀態都是由上一層的狀態推導而來，所以也可以使用滾動數組來進行優化。

動態規劃五部曲

確定dp數組以及下標的含義

dp[j] 表示背包重量為 weightp[j] 時，可以獲得的最大價值。

確定遞推公式

二維dp數組的遞推公式為： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
一維dp數組，其實就上一層 dp[i-1] 這一層 拷貝的 dp[i]來。
所以在 上面遞推公式的基礎上，去掉i這個維度就好。

遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

以下為分析：

dp[j] 為 容量為j的背包所背的最大價值。

dp[j] 可以通過 dp[j] - weight[i]] 推導出來，dp[j] - weight[i]] 表示容量為 j - weight[i] 的背包所背的最大價值。

dp[j - weight[i]] + value[i] 表示 容量為 [j - 物品i重量] 的背包 加上 物品 i 的價值。（也就是容量為 j 的背包，放入物品 i 了之后的價值即：dp[j] ）

此時 dp[j] 有兩個選擇，一個是取自己 dp[j] 相當于 二維dp數組中的 dp[i-1][j] ，即不放物品 i，一個是取 dp[j - weight[i]] + value[i] ，即放物品 i ，指定是取最大的，畢竟是求最大價值。

初始化dp數組

dp數組初始化的時候，都初始為 0 即可。

確定遍歷順序

我們在二維dp數組的時候，遍歷順序沒有要求，但是對于一維數組，這里有嚴格的順序。
我們的滾動數組的思想是當前層是由上一層拷貝而來，而每一層代表的是物品，所以我們要先便遍歷物品，再遍歷背包重量。

在遍歷背包重量的時候，一定要倒序遍歷。

因為在某一層，當前數值是由他左面推導而來，如果我們正序遍歷的話，新的值會覆蓋掉原來的值，這樣也就導致了某一個物品被多次使用。

代碼

n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [0] * (bagweight + 1)  # 創建一個動態規劃數組dp，初始值為0dp[0] = 0  # 初始化dp[0] = 0,背包容量為0，價值最大為0for i in range(n):  # 應該先遍歷物品，如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品for j in range(bagweight, weight[i]-1, -1):  # 倒序遍歷背包容量是為了保證物品i只被放入一次dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagweight])

三、Leetcode 416. 分割等和子集

給你一個 只包含正整數的 非空 數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。
示例：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

引用：

原文鏈接：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
題目鏈接：https://leetcode.cn/problems/partition-equal-subset-sum/description/
視頻講解：https://www.bilibili.com/video/BV1rt4y1N7jE/

解決的問題是判斷集合里能否出現總和為 sum / 2 的子集，這相當于有一個只能裝重量為 sum / 2 的背包，商品就是集合里的數字，要判斷這些數字能否把背包裝滿。
對于這些數字商品而言，它們只有一個維度，即重量等于價值。當這些數字能裝滿承載重量為 sum / 2 的背包時，背包的價值也為 sum / 2。
所以此問題可轉化為裝滿承載重量為 sum / 2 的背包時，其最大價值是多少，若最大價值是 sum / 2，就說明背包正好被商品裝滿，由于商品是數字且重量和價值相同，因此可以直接用 01 背包來解決這個問題。

動態規劃五部曲

確定dp數組以及下標的含義

dp[j] 表示背包重量為 weightp[j] 時，可以獲得的最大價值。

確定遞推公式

背包問題的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
那么這里重量和價值在同一個維度，所以我們的遞推公式改寫為
dp[j]=max(dp[j], dp[j-nums[i]]+nums[i])

初始化dp數組

dp數組初始化的時候，都初始為 0 即可。

確定遍歷順序

和我們01背包問題中的一維滾動數組遍歷方式一樣。

代碼

class Solution:def canPartition(self, nums: List[int]) -> bool:total_sum = sum(nums)if total_sum % 2 != 0:return Falsetarget = int(total_sum / 2)dp = [0] * (target+1)for i in range(len(nums)):for j in range(target, nums[i]-1, -1):dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])return dp[target]==target