Hello 演算法 0-1 背包問題逐步視覺化：knapsack.md 與 knapsack.py 四種解法全剖析-开发者社区

Hello 演算法 0-1 背包問題逐步視覺化：knapsack.md 與 knapsack.py 四種解法全剖析

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文以《Hello 演算法》繁體中文倉庫中的 zh-hant/codes/pythontutor/chapter_dynamic_programming/knapsack.md 為核心線索，逐則解析其中內嵌的 0-1 背包 PythonTutor 視覺化執行連結，並與對應的 knapsack.py 原始碼互相印證。讀者讀完本文後，將能完整掌握 0-1 背包問題從暴力搜尋、記憶化搜尋、二維動態規劃到空間最佳化動態規劃的完整演進脈絡，理解每種方法的狀態定義、轉移方程、邊界條件與時間／空間複雜度差異。

這份文件在倉庫中的定位與使用方式

在《Hello 演算法》的程式碼組織中，codes/python下存放的是可執行的 Python 範例，而codes/pythontutor則存放一批特殊的 Markdown 文件——每份文件對應一個演算法章節，內容是一則則「PythonTutor 視覺化執行」的入口連結，方便讀者直接在網頁上逐行觀察程式執行過程。

以 knapsack.md 為例，全文由四組內容構成，每組皆遵循同一種模板：

一行 HTML 註解標記，例如，用來標示這段程式碼對應的原始檔與函式；
一行指向 PythonTutor 網頁的長連結，其網址透過 URL 編碼把 Python 原始碼與參數直接內嵌在查詢字串中（例如py=311表示以 Python 3.11 執行、mode=display表示以逐步顯示模式開啟、curInstr=7大致對應頁面開啟後停留的指令游標位置）。

四組內容分別對應 0-1 背包問題的四種解法：

標記中的函式	解法階段	對應方法
`knapsack_dfs`	暴力搜尋	方法一
`knapsack_dfs_mem`	記憶化搜尋	方法二
`knapsack_dp`	二維表動態規劃	方法三
`knapsack_dp_comp`	一維空間最佳化動態規劃	方法四

書中關於「視覺化執行」的整體機制說明見 suggestions.md：網頁版支援基於 PythonTutor 的 Python 程式碼視覺化執行，讀者可展開程式碼區塊下方檢視、觀察執行過程，也可切換成全螢幕觀看。而本章完整的理論推導、決策樹模型與逐步填充 $dp$ 表的圖解，則收錄於章節文件 knapsack_problem.md。建議搭配閱讀：先由章節文件理解「為什麼」，再用 PythonTutor 連結觀察「程式怎麼跑」。

0-1 背包問題：先建立完整的解法地圖

本節先交代問題本身與四種解法共享的數學骨架，方便後續逐則視覺化時對號入座。

問題定義與狀態設計

章節文件給出的問題定義如下：給定 $n$ 個物品，第 $i$ 個物品的重量為 $wgt[i-1]$、價值為 $val[i-1]$，以及一個容量為 $cap$ 的背包，每個物品只能選擇一次，求在限定背包容量下能放入物品的最大價值。由於物品編號 $i$ 從 $1$ 開始計數而陣列索引從 $0$ 開始計數，因此程式碼中第 $i$ 個物品對應的是wgt[i - 1]與val[i - 1]。

解題的關鍵是狀態設計與最優子結構分析：

狀態：記為 $[i, c]$，其中 $i$ 是當前考慮到的物品編號、$c$ 是背包剩餘容量；
子問題：$dp[i, c]$ 代表「前 $i$ 個物品在容量為 $c$ 的背包中的最大價值」，最終待求解的是 $dp[n, cap]$，需要一張 $(n+1) \times (cap+1)$ 的 $dp$ 表；
決策分支：不放入物品 $i$ 時狀態轉為 $[i-1, c]$；放入物品 $i$ 時容量減少 $wgt[i-1]$、價值增加 $val[i-1]$，狀態轉為 $[i-1, c-wgt[i-1]]$；
狀態轉移方程：$dp[i, c] = \max(dp[i-1, c],\ dp[i-1, c - wgt[i-1]] + val[i-1])$；
邊界條件：無物品（$i=0$）或背包容量為 $0$（$c=0$）時，最大價值皆為 $0$。

驅動資料與輸出

四種解法共用同一組測試資料（見原始碼中的 Driver Code）：

wgt = [10, 20, 30, 40, 50] # 物品重量 val = [50, 120, 150, 210, 240] # 物品價值 cap = 50 # 背包容量 n = len(wgt)

執行後統一以print(f"不超過背包容量的最大物品價值為 {res}")輸出結果。無論用哪一種方法，最終印出的最大值都應一致，這也正是逐個函式獨立驗證結果正確性的好素材。

方法一：`knapsack_dfs`暴力搜尋——先看遞迴怎麼展開

文件中的第一則視覺化連結對應暴力搜尋版本。它的遞迴要素如下：

遞迴參數：狀態 $[i, c]$，由物品編號與剩餘容量共同描述；
返回值：子問題的解 $dp[i, c]$；
終止條件：物品編號越界 $i = 0$ 或剩餘容量 $c = 0$ 時回傳價值 $0$；
剪枝：若當前物品重量wgt[i - 1]超過剩餘容量c，則只能選擇不放入，直接遞迴求解(i - 1, c)。

核心實作如下：

def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int: """0-1 背包：暴力搜尋""" # 若已選完所有物品或背包無剩餘容量，則返回價值 0 if i == 0 or c == 0: return 0 # 若超過背包容量，則只能選擇不放入背包 if wgt[i - 1] > c: return knapsack_dfs(wgt, val, i - 1, c) # 計算不放入和放入物品 i 的最大價值 no = knapsack_dfs(wgt, val, i - 1, c) yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1] # 返回兩種方案中價值更大的那一個 return max(no, yes)

其中no對應「不放入物品 i」、yes對應「放入物品 i」，兩者取最大值。在視覺化頁面上可以清楚看到：每次呼叫knapsack_dfs都會在遞迴樹上分裂出兩條分支，因此時間複雜度為 $O(2^n)$——這是四種方法中最慢的。

上圖展示的暴力搜尋遞迴樹揭示了一個關鍵缺點：存在大量重疊子問題。例如 $dp[1, 10]$ 這類狀態會在不同分支中被重複求解；當物品數量與背包容量變大、尤其是有多個相同重量的物品時，重疊子問題的數量會急遽增加，白白浪費計算。這個觀察正是引出方法二（記憶化）的直接動機。

方法二：`knapsack_dfs_mem`記憶化搜尋——把算過的結果記下來

第二則視覺化連結對應記憶化搜尋版本。它與暴力搜尋的唯一差別，是引入了一張「備忘錄」mem，其中mem[i][c]對應 $dp[i, c]$：遞迴前先查表，若已有紀錄（不等於初始值-1）就直接回傳，保證每個重疊子問題只被計算一次。

def knapsack_dfs_mem( wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int ) -> int: """0-1 背包：記憶化搜尋""" # 若已選完所有物品或背包無剩餘容量，則返回價值 0 if i == 0 or c == 0: return 0 # 若已有記錄，則直接返回 if mem[i][c] != -1: return mem[i][c] # 若超過背包容量，則只能選擇不放入背包 if wgt[i - 1] > c: return knapsack_dfs_mem(wgt, val, mem, i - 1, c) # 計算不放入和放入物品 i 的最大價值 no = knapsack_dfs_mem(wgt, val, mem, i - 1, c) yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1] # 記錄並返回兩種方案中價值更大的那一個 mem[i][c] = max(no, yes) return mem[i][c]

呼叫端需要先初始化這張表：mem = [[-1] * (cap + 1) for _ in range(n + 1)]。之所以用-1當「尚未計算」的哨兵值，是因為 0-1 背包的最大價值下限是 $0$，-1不會與任何合法答案混淆。

引入記憶化之後，每個狀態 $[i, c]$ 至多被求解一次，時間複雜度取決於子問題的總數，即 $O(n \times cap)$，與 $O(2^n)$ 的暴力法相比是數量級上的躍升。上圖即展示了在記憶化搜尋中被「剪掉」、不必再走的分支。

方法三：`knapsack_dp`動態規劃——從「遞迴＋查表」改為「迭代填表」

記憶化搜尋本質上仍是自頂向下的遞迴；第三則視覺化連結則把流程翻轉成自底向上的迭代填表，這便是標準動態規劃寫法：

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int: """0-1 背包：動態規劃""" n = len(wgt) # 初始化 dp 表 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: # 若超過背包容量，則不選物品 i dp[i][c] = dp[i - 1][c] else: # 不選和選物品 i 這兩種方案的較大值 dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) return dp[n][cap]

幾個值得在視覺化頁面上逐一核對的細節：

初始化：dp = [[0] * (cap + 1) for _ in range(n + 1)]讓首行dp[0][c]（沒有物品）與首列dp[i][0]（容量為 0）天然等於 $0$，正好對應邊界條件，不需額外賦值；
走訪順序：外層迴圈按物品 $i$ 正序、內層迴圈按容量 $c$ 正序掃描。由於 $dp[i][c]$ 只依賴上一行的正上方 $dp[i-1][c]$ 與左上方 $dp[i-1][c-wgt[i-1]]$，這種順序能保證轉移時所需的舊值都尚未被覆蓋；
容量不足處理：當wgt[i - 1] > c時，放不下物品 $i$，直接沿用dp[i - 1][c]。

該方法的時間與空間複雜度都由 $dp$ 表大小決定，皆為 $O(n \times cap)$。在 PythonTutor 逐步模式下，讀者可以對照章節文件 knapsack_problem.md 中 <1>～<14> 的分步圖，逐格確認 $dp$ 表的填寫順序。

方法四：`knapsack_dp_comp`空間最佳化——一個陣列＋倒序走訪

第四則視覺化連結對應空間最佳化版本，這是本章最具「巧思」的一步。觀察狀態轉移可發現：$dp[i][c]$ 只與上一行（$i-1$）的狀態有關，與更早的行無關。因此可以把 $dp$ 表從二維壓縮成一維陣列，僅保留「目前這一行」，讓空間複雜度從 $O(n \times cap)$ 降到 $O(cap)$。

但壓縮後出現一個陷阱：如果容量 $c$ 仍採正序（由小到大）走訪，當計算到較大的c時，左上方dp[c - wgt[i - 1]]可能已經在本次外層迴圈中被覆蓋成第 $i$ 行的新值，導致狀態轉移出錯。解法是將內層迴圈改為倒序走訪（由cap遞減到 1），這樣讀取dp[c - wgt[i - 1]]時，它仍是第 $i-1$ 行的舊值，不會被提前覆蓋。

def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int: """0-1 背包：空間最佳化後的動態規劃""" n = len(wgt) # 初始化 dp 表 dp = [0] * (cap + 1) # 狀態轉移 for i in range(1, n + 1): # 倒序走訪 for c in range(cap, 0, -1): if wgt[i - 1] > c: # 若超過背包容量，則不選物品 i dp[c] = dp[c] else: # 不選和選物品 i 這兩種方案的較大值 dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) return dp[cap]

原始碼中if wgt[i - 1] > c: dp[c] = dp[c]這一行是刻意保留的「自我賦值」，目的在於讓程式與轉移方程的分支結構一一對應、便於教學閱讀；實際上它不改變任何狀態。理解這段程式時，也可以對照 knapsack_problem.md 中「從第 $i=1$ 行轉換到第 $i=2$ 行」的六步示意圖（knapsack_dp_comp_step1至knapsack_dp_comp_step6），體會正序走訪與倒序走訪的差別。

四種方法一表對比

在視覺化頁面上把四則連結輪流跑過一遍後，可以整理成下表，方便日後複習或面試速查：

方法	函式	核心資料結構	時間複雜度	空間複雜度	關鍵要點
暴力搜尋	`knapsack_dfs`	遞迴樹	$O(2^n)$	$O(n)$（遞迴深度）	每個物品都分裂成選／不選兩條分支，存在大量重疊子問題
記憶化搜尋	`knapsack_dfs_mem`	`mem`備忘錄 + 遞迴	$O(n \times cap)$	$O(n \times cap)$	用`-1`哨兵值表示「未計算」，命中即回傳
動態規劃	`knapsack_dp`	二維 $dp$ 表	$O(n \times cap)$	$O(n \times cap)$	自底向上雙層正序填表，首行首列天然為 0
空間最佳化 DP	`knapsack_dp_comp`	一維`dp`陣列	$O(n \times cap)$	$O(cap)$	內層容量必須倒序走訪，避免覆蓋左上方舊值

可以看到：從方法二開始，四者共享同一條狀態轉移方程，差別只在「要不要記錄重複結果」與「用多大空間記錄」。先能流利推導轉移方程，再理解一維倒序走訪的必要性，0-1 背包在動態規劃題型中的骨架就牢牢掌握了。

如何在倉庫中對照與執行

若想在本地親手驗證與視覺化內容完全一致的行為，可依循以下步驟：

閱讀原始碼：直接開啟 zh-hant/codes/python/chapter_dynamic_programming/knapsack.py。檔案內依序定義knapsack_dfs、knapsack_dfs_mem、knapsack_dp、knapsack_dp_comp四個函式，並在if __name__ == "__main__":的 Driver Code 中依序呼叫，四段程式與 PythonTutor 視覺化內容完全對應（簡體中文版本的同名原始檔位於 codes/python/chapter_dynamic_programming/knapsack.py）；
執行驗證：在有 Python 環境的機器上執行python knapsack.py，四種方法會印出相同的最大價值結果——若輸出不致，即可立即察覺某一版實作或狀態轉移有誤；
逐行觀察：在《Hello 演算法》網頁版對應程式碼區塊下方展開「視覺化執行」，即會載入 PythonTutor 頁面；重點觀察方法四的容量迴圈是否為倒序，以及改為正序後答案是否會變錯，這是理解空間最佳化精髓的最佳實驗；
深入原理：對照章節文件 knapsack_problem.md 中的決策樹、遞迴樹與 $dp$ 表填充圖，把「圖解」與「程式步進」兩條學習路徑交織起來，理解會更立體。

總結

knapsack.md 雖然外觀只是四則視覺化連結，背後卻濃縮了 0-1 背包問題最完整的解法譜系：先從 $O(2^n)$ 的暴力遞迴確認決策樹模型，再用記憶化消除重疊子問題，進而以迭代動態規劃穩定到 $O(n \times cap)$，最後用一維陣列與倒序走訪把空間壓到 $O(cap)$。把每一則連結對應的程式碼讀懂、跑通、並在章節圖解的輔助下想清楚「為什麼倒序」，你掌握的就不只是背包問題本身，而是一整套可遷移到其他動態規劃題型的分析框架。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

Hello 演算法 0-1 背包問題逐步視覺化：knapsack.md 與 knapsack.py 四種解法全剖析