0/1 背包問題

問題定義

你有 N 個物品，每個物品有重量 w[i] 與價值 v[i]。你有一個容量為 W 的背包。每個物品只能選 0 或 1 次。如何選取才能讓總價值最大？

Vibe Prompt

「幫我用 DP 解決 0/1 背包問題：N=5, W=10, 物品=[(2,6),(5,9),(4,5),(3,7),(6,8)]。輸出 dp 表格與選取的物品。」

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    # 回溯選取的物品
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][capacity], selected

# 範例
weights = [2, 5, 4, 3, 6]
values = [6, 9, 5, 7, 8]
capacity = 10
max_val, items = knapsack_01(weights, values, capacity)
print(f"最大價值: {max_val}")
print(f"選取物品: {items}")