背包问题（Knapsack Problem）是计算机科学中一个经典的问题，它属于组合优化问题。背包问题有多种变体，其中最著名的是 0/1 背包问题。

0/1 背包问题

0/1 背包问题是指给定一组物品，每个物品都有一定的价值和重量，再给定一个背包，背包有一定的承重限制。问题是在不超过背包承重限制的情况下，如何选择物品，使得背包中的物品总价值最大。

解决方法

解决 0/1 背包问题常用的方法是动态规划（Dynamic Programming，DP）。

  • 状态定义：dp[i][w] 表示在前 i 个物品中选择，且背包容量为 w 时的最大价值。
  • 状态转移方程：
    • 如果不选择第 i 个物品，则 dp[i][w] = dp[i-1][w]
    • 如果选择第 i 个物品，则 dp[i][w] = dp[i-1][w-w[i]] + w[i]（前提是 w-w[i] >= 0）
    • 最终结果为 dp[n][W]，其中 n 是物品数量，W 是背包容量。

示例

假设有 4 个物品，价值分别为 60、100、120、130，重量分别为 10、20、30、40，背包容量为 50。

def knapsack(W, weights, values, n):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]],  dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

values = [60, 100, 120, 130]
weights = [10, 20, 30, 40]
W = 50
n = len(values)
print(knapsack(W, weights, values, n))

输出结果为 220，表示背包中的物品总价值最大为 220。

扩展阅读

更多关于背包问题的案例研究，可以参考LeetCode 案例研究。

Knapsack Problem