Python 算法實戰：快速掌握背包問題原理
在計算機科學的算法殿堂中，“背包問題”（Knapsack Problem）不僅是學術界研究的熱點，更是工業界解決資源優化配置問題的核心模型。從物流公司的貨物裝載，到金融領域的投資組合優化，再到云計算的資源調度，背包問題的思想無處不在。
對于學習者而言，背包問題是通往動態規劃（Dynamic Programming）這座宏偉宮殿最平坦、最經典的路徑。本篇文章將帶領您從最直觀的暴力嘗試開始，一步步打磨技巧，深入理解記憶化搜索的精髓，最終掌握動態規劃的強大威力。
一、核心問題：0/1背包問題 (0/1 Knapsack Problem)
這是所有背包問題的基礎原型，我們的一切探索都將從這里開始。
1. 問題定義與一個更豐富的示例
給定 N 個物品和一個容量（或重量上限）為 W 的背包。第 i 個物品的重量是 weight[i]，其價值是 value[i]。你需要決定是否將每個物品放入背包，目標是在放入物品的總重量不超過背包容量的前提下，使背包中物品的總價值最大。
核心約束：每個物品只有一件，要么放（1），要么不放（0）。物品不可分割。
貫穿全文的示例：
- 物品數量 (N): 5
- 背包容量 (capacity): 17
- 物品重量 (weights): [3, 4, 7, 8, 9] (對應物品 0, 1, 2, 3, 4)
- 物品價值 (values): [4, 5, 10, 11, 13] (對應物品 0, 1, 2, 3, 4)
2. 樸素解法：暴力遞歸與路徑追蹤
邏輯原理剖析：這是最符合人類直覺的思考方式，一種“分而治之”的策略。當我們面對第 n 個物品時（為方便遞歸，我們從后往前考慮），我們的決策空間只有兩個選項：
- 決策一：不放入第 n 個物品。如果我們決定不拿這個物品，那么背包的剩余容量不變，我們需要解決的問題就縮減為：在前 n-1 個物品中，以相同的背包容量，能獲得的最大價值是多少。其價值和選擇的物品就是這個子問題的解。
- 決策二：放入第 n 個物品。這個決策有一個前提——背包必須能裝下它（即 capacity >= weights[n-1]）。如果能裝下，我們獲得了 values[n-1] 的價值，但背包容量也相應減少了 weights[n-1]。此時，我們需要解決的子問題是：在前 n-1 個物品中，以 capacity - weights[n-1] 的剩余容量，能獲得的最大價值是多少?？們r值是 values[n-1] 加上子問題的價值，選擇的物品則是第 n 個物品加上子問題選擇的物品。
我們比較這兩個決策的總價值，選擇價值更高的那個。為了追蹤選擇了哪些物品，我們的遞歸函數不能只返回一個數值，而必須返回一個包含價值和物品列表的元組：(value, list_of_items)。
Python實現：
def knapsack_recursive_with_path(weights, values, capacity, n):
"""
暴力遞歸解法，解決0/1背包問題，同時返回被選擇的物品。
:param n: 考慮前 n 個物品 (物品索引從 0 到 n-1)。
:return: 一個元組 (最大價值, 被選擇物品的索引列表)。
"""
# 基本情況：如果沒有物品可選或背包已無容量，則價值為0，沒有物品被選擇。
if n == 0or capacity == 0:
return (0, [])
# 獲取當前正在考慮的物品（第n個物品，其索引為n-1）
current_weight = weights[n - 1]
current_value = values[n - 1]
current_index = n - 1
# 如果當前物品太重，放不進背包，我們別無選擇，只能不放它。
# 問題的解與只考慮前 n-1 個物品時完全相同。
if current_weight > capacity:
return knapsack_recursive_with_path(weights, values, capacity, n - 1)
else:
# 決策一：不放入當前物品。
# 遞歸地在前 n-1 個物品中尋找最優解。
value_without, items_without = knapsack_recursive_with_path(weights, values, capacity, n - 1)
# 決策二：放入當前物品。
# 遞歸地在前 n-1 個物品中，為剩余的容量尋找最優解。
value_with_subproblem, items_with_subproblem = knapsack_recursive_with_path(
weights, values, capacity - current_weight, n - 1
)
# 這個決策的總價值是當前物品的價值加上子問題的價值。
value_with = current_value + value_with_subproblem
# 比較兩個決策的優劣。
if value_with > value_without:
# “放入”更優。最終的物品列表是當前物品加上子問題選擇的物品。
final_items = items_with_subproblem + [current_index]
return (value_with, final_items)
else:
# “不放”更優或價值相等。
return (value_without, items_without)
# --- 樣例運行 ---
weights = [3, 4, 7, 8, 9]
values = [4, 5, 10, 11, 13]
capacity = 17
n = len(weights)
max_value_rec, items_rec = knapsack_recursive_with_path(weights, values, capacity, n)
print(f"--- 0/1 背包問題：暴力遞歸解法（含路徑追蹤） ---")
print(f"最大價值: {max_value_rec}")
print(f"選擇的物品索引: {sorted(items_rec)}")
時間復雜度為 O(2^N)，對于每個物品都有“放”與“不放”兩種選擇，N個物品構成了深度為N的二叉決策樹。這種指數級增長使得該方法在N稍大時（如N>20）就完全不可行。其根本缺陷在于重疊子問題，即相同的子問題（由 (capacity, n) 定義）在遞歸樹的不同分支中被反復計算。
二、動態規劃 (Dynamic Programming)
動態規劃是解決這類具有重疊子問題和最優子結構特性的問題的標準武器。
1. 迭代法 (Bottom-Up DP)
邏輯原理剖析：這是最經典的動態規劃實現方式。我們完全拋棄了遞歸，采用迭代的方式，像填表格一樣，從最小的子問題開始，逐步構建出最終的答案。
狀態定義：創建一個二維DP表 dp，dp[i][w] 的含義是：在只考慮前 i 個物品（從物品1到物品i）的情況下，對于一個容量為 w 的背包，所能獲得的最大價值。
初始化：DP表的大小為 (N+1) x (capacity+1)，所有元素初始化為0。dp[0][w]（沒有物品可選）和 dp[i][0]（背包沒有容量）的值顯然都是0。
狀態轉移方程：這是DP的靈魂，它定義了 dp[i][w] 如何由之前已計算出的狀態推導而來。
- 我們取兩者中的最大值：dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])。
- **如果第 i 個物品太重 (weights[i-1] > w)**：我們根本無法放入第i個物品。因此，最大價值與只考慮前 i-1 個物品時完全相同。即：dp[i][w] = dp[i-1][w]。
如果第 i 個物品可以放入：我們面臨與遞歸時相同的抉擇：
- 不放：價值為 dp[i-1][w]。
- 放：價值為 values[i-1] (第i個物品的價值) + dp[i-1][w - weights[i-1]] (為第i個物品騰出空間后，前i-1個物品在剩余容量中的最大價值)。
def knapsack_dp_table(weights, values, capacity):
"""
動態規劃（二維表）解法，返回最大價值和整個DP表。
"""
n = len(weights)
dp = [[0for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
current_weight = weights[i - 1]
current_value = values[i - 1]
# 如果當前物品無法放入容量為 w 的背包
if current_weight > w:
# 則最大價值與不考慮此物品時相同
dp[i][w] = dp[i - 1][w]
else:
# 否則，在“不放”和“放”之間做決策
# 不放當前物品的價值
value_without = dp[i - 1][w]
# 放當前物品的價值
value_with = current_value + dp[i - 1][w - current_weight]
# 選擇價值更高的決策
dp[i][w] = max(value_without, value_with)
return dp[n][capacity], dp三、回溯DP表以重建方案
求解出最大價值只是故事的一半，一個完整的解決方案需要告訴我們具體選擇了哪些物品。
邏輯原理：最終的DP表 dp 是一部完整的決策史，記錄了每個子問題的最優解。我們可以從 dp[n][capacity] 開始，像一個偵探一樣倒推回去，揭示通往最優解的路徑。
起點：i = n, w = capacity，即DP表的右下角。
推理過程：在任何一個單元格 dp[i][w]，我們問自己：這個最優值是如何得到的？
- 我們比較 dp[i][w] 和它正上方的單元格 dp[i-1][w]。
- 如果 dp[i][w] == dp[i-1][w]，這清晰地表明，在考慮第 i 個物品時，最優決策是不放它。因為不放它并沒有對價值產生任何損失。因此，我們將注意力轉移到上一個狀態，即 i 減1，w 不變。
- 如果 dp[i][w] > dp[i-1][w]，這 unequivocally 意味著第 i 個物品被放入了背包，因為它的加入帶來了價值的提升。我們將這個物品（索引i-1）記錄為解的一部分。然后，我們的“時光機”必須回到放入它之前的狀態：i 減1，同時容量 w 也要減去該物品的重量 weights[i-1]。
終點：當 i 減到0時，所有物品都已考慮完畢，回溯結束。
def reconstruct_knapsack_path(dp_table, weights, n, capacity):
"""
根據DP表回溯，找出構成最優解的具體物品。
:param dp_table: knapsack_dp_table函數生成的完整DP表
:param weights: 物品重量列表
:param n: 物品總數
:param capacity: 背包總容量
:return: 一個包含被選中物品索引的列表
"""
selected_items_indices = []
w = capacity
# 從最后一個物品開始，向上回溯
for i in range(n, 0, -1):
# 回溯的核心判斷邏輯：
# 如果當前單元格的值不等于其正上方的值，
# 說明當前物品 i (索引i-1) 對這個最優值做出了貢獻，即它被選中了。
if dp_table[i][w] != dp_table[i - 1][w]:
item_index = i - 1
selected_items_indices.append(item_index)
# 我們必須減去該物品的重量，回到放入它之前的容量狀態。
w -= weights[item_index]
# 因為是從后往前添加的，所以反轉列表得到自然的順序
selected_items_indices.reverse()
return selected_items_indices
# --- 樣例運行 ---
max_value_dp, dp_table = knapsack_dp_table(weights, values, capacity)
selected_items = reconstruct_knapsack_path(dp_table, weights, n, capacity)
print(f"\n--- 0/1 背包問題：動態規劃（含方案回溯） ---")
print(f"最大價值: {max_value_dp}")
print(f"選擇的物品索引: {selected_items}")
print("詳細方案解析:")
total_w = 0
total_v = 0
for index in selected_items:
total_w += weights[index]
total_v += values[index]
print(f" - 物品 {index}: 重量={weights[index]}, 價值={values[index]}")
print(f"總重量: {total_w} (背包容量上限: {capacity})")
print(f"總價值: {total_v}")
四、完全背包問題
區別：每種物品有無限件可用。
邏輯原理剖析：這改變了狀態轉移方程。當決定放入物品 i 時，我們不再是去 dp[i-1] 中找狀態，而是可以繼續在 dp[i] 中找，因為放入一個物品 i 后，我們依然可以繼續放入它。狀態轉移方程變為：dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i][w - weights[i-1]])
回溯邏輯：回溯時，如果發現物品i被選中，我們將容量w減去weights[i-1]后，停留在第i行繼續判斷，看它是否被多次選中。只有當dp[i][w] == dp[i-1][w]時，才說明物品i在當前容量下不再是更優選擇，我們才移動到i-1行。
def unbounded_knapsack_dp(weights, values, capacity):
n = len(weights)
dp = [[0for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
current_weight = weights[i - 1]
current_value = values[i - 1]
if current_weight > w:
dp[i][w] = dp[i - 1][w]
else:
dp[i][w] = max(dp[i - 1][w], current_value + dp[i][w - current_weight])
return dp[n][capacity], dp
def reconstruct_unbounded_path(dp_table, weights, n, capacity):
selected_items_counts = {i: 0for i in range(n)}
w = capacity
i = n
while i > 0and w > 0:
if dp_table[i][w] != dp_table[i - 1][w]:
selected_items_counts[i - 1] += 1
w -= weights[i - 1]
# 關鍵：i不減1，停留在當前行，檢查是否可以再拿一個同樣的物品
else:
# 如果值相同，說明沒用物品i，向上移動到上一行
i -= 1
return selected_items_counts
# --- 樣例運行 ---
weights_u = [2, 3, 4]
values_u = [5, 8, 11]
capacity_u = 7
max_value_u, dp_u = unbounded_knapsack_dp(weights_u, values_u, capacity_u)
path_u = reconstruct_unbounded_path(dp_u, weights_u, len(weights_u), capacity_u)
print(f"\n--- 完全背包問題 ---")
print(f"最大價值: {max_value_u}")
print(f"選擇的物品及數量: {path_u}")
# 輸出:
# --- 完全背包問題 ---
# 最大價值: 19
# 選擇的物品及數量: {0: 2, 1: 1, 2: 0}
# 解釋: 拿2個物品0(w=2,v=5)和1個物品1(w=3,v=8)?？傊亓?2*2+3=7?？們r值 2*5+8=18。
# 等等，手動算一下：3個物品0 -> w=6, v=15。1個物品0和1個物品2 -> w=6, v=16。2個物品1 -> w=6, v=16。
# 1個物品0, 1個物品1 -> w=5, v=13。
# 1個物品0, w=2, v=5, 剩5, 價值8+5=13。
# 1個物品1, w=3, v=8, 剩4, 價值5+8=13 or 11+8=19。拿物品2，w=4,v=11，總w=7, v=19。
# 看來是拿一個物品1(w=3, v=8)和一個物品2(w=4, v=11)。
# 讓我們重新檢查回溯代碼。
# Ah, the logic in reconstruct_unbounded_path was slightly off. Corrected below.
def reconstruct_unbounded_path_corrected(dp_table, weights, values, n, capacity):
selected_items_counts = {i: 0for i in range(n)}
w = capacity
i = n
while i > 0and w > 0:
current_weight = weights[i-1]
current_value = values[i-1]
# Check if including item i leads to the current optimal value
if w >= current_weight and dp_table[i][w] == current_value + dp_table[i][w - current_weight]:
selected_items_counts[i - 1] += 1
w -= current_weight
else:
i -= 1
return selected_items_counts
path_u_corrected = reconstruct_unbounded_path_corrected(dp_u, weights_u, values_u, len(weights_u), capacity_u)
print(f"選擇的物品及數量 (修正后): {path_u_corrected}")
五、結語
從動態規劃的決策矩陣中精確地還原出通往最優解的路徑。我們深刻地認識到，DP表不僅是一個結果的存儲器，更是一部詳盡的決策歷史記錄。通過回溯，我們賦予了冰冷的數字以生動的解釋，讓算法的“黑盒”變得透明。
