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 註解標記例如!-- [file]{knapsack}-[class]{}-[func]{knapsack_dfs} --用來標示這段程式碼對應的原始檔與函式一行指向 PythonTutor 網頁的長連結其網址透過 URL 編碼把 Python 原始碼與參數直接內嵌在查詢字串中例如py311表示以 Python 3.11 執行、modedisplay表示以逐步顯示模式開啟、curInstr7大致對應頁面開啟後停留的指令游標位置。四組內容分別對應 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]$需要一張 $(n1) \times (cap1)$ 的 $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])$邊界條件無物品$i0$或背包容量為 $0$$c0$時最大價值皆為 $0$。驅動資料與輸出四種解法共用同一組測試資料見原始碼中的 Driver Codewgt [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 中 114 的分步圖逐格確認 $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 中「從第 $i1$ 行轉換到第 $i2$ 行」的六步示意圖knapsack_dp_comp_step1至knapsack_dp_comp_step6體會正序走訪與倒序走訪的差別。四種方法一表對比在視覺化頁面上把四則連結輪流跑過一遍後可以整理成下表方便日後複習或面試速查方法函式核心資料結構時間複雜度空間複雜度關鍵要點暴力搜尋knapsack_dfs遞迴樹$O(2^n)$$O(n)$遞迴深度每個物品都分裂成選不選兩條分支存在大量重疊子問題記憶化搜尋knapsack_dfs_memmem備忘錄 遞迴$O(n \times cap)$$O(n \times cap)$用-1哨兵值表示「未計算」命中即回傳動態規劃knapsack_dp二維 $dp$ 表$O(n \times cap)$$O(n \times cap)$自底向上雙層正序填表首行首列天然為 0空間最佳化 DPknapsack_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)$。把每一則連結對應的程式碼讀懂、跑通、並在章節圖解的輔助下想清楚「為什麼倒序」你掌握的就不只是背包問題本身而是一整套可遷移到其他動態規劃題型的分析框架。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 註解標記例如!-- [file]{knapsack}-[class]{}-[func]{knapsack_dfs} --用來標示這段程式碼對應的原始檔與函式一行指向 PythonTutor 網頁的長連結其網址透過 URL 編碼把 Python 原始碼與參數直接內嵌在查詢字串中例如py311表示以 Python 3.11 執行、modedisplay表示以逐步顯示模式開啟、curInstr7大致對應頁面開啟後停留的指令游標位置。四組內容分別對應 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]$需要一張 $(n1) \times (cap1)$ 的 $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])$邊界條件無物品$i0$或背包容量為 $0$$c0$時最大價值皆為 $0$。驅動資料與輸出四種解法共用同一組測試資料見原始碼中的 Driver Codewgt [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 中 114 的分步圖逐格確認 $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 中「從第 $i1$ 行轉換到第 $i2$ 行」的六步示意圖knapsack_dp_comp_step1至knapsack_dp_comp_step6體會正序走訪與倒序走訪的差別。四種方法一表對比在視覺化頁面上把四則連結輪流跑過一遍後可以整理成下表方便日後複習或面試速查方法函式核心資料結構時間複雜度空間複雜度關鍵要點暴力搜尋knapsack_dfs遞迴樹$O(2^n)$$O(n)$遞迴深度每個物品都分裂成選不選兩條分支存在大量重疊子問題記憶化搜尋knapsack_dfs_memmem備忘錄 遞迴$O(n \times cap)$$O(n \times cap)$用-1哨兵值表示「未計算」命中即回傳動態規劃knapsack_dp二維 $dp$ 表$O(n \times cap)$$O(n \times cap)$自底向上雙層正序填表首行首列天然為 0空間最佳化 DPknapsack_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)$。把每一則連結對應的程式碼讀懂、跑通、並在章節圖解的輔助下想清楚「為什麼倒序」你掌握的就不只是背包問題本身而是一整套可遷移到其他動態規劃題型的分析框架。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考