跳到主要内容

0-1 背包问题

介绍​

0-1 背包问题是动态规划中的经典问题之一。它描述的是：给定一组物品，每个物品都有一个重量和一个价值，在限定的背包容量内，如何选择物品使得背包中的总价值最大。这里的“0-1”意味着每个物品只能选择放入背包（1）或不放入背包（0），不能部分放入。

这个问题在现实生活中非常常见，例如在资源有限的情况下如何最大化收益，或者在旅行时如何选择最有价值的物品装入行李箱。

问题定义​

假设我们有 n 个物品和一个容量为 W 的背包。每个物品 i 有一个重量 w[i] 和一个价值 v[i]。我们的目标是选择一些物品放入背包，使得这些物品的总重量不超过 W，且总价值最大。

动态规划解法​

1. 定义状态​

我们可以使用一个二维数组 dp[i][j] 来表示前 i 个物品在背包容量为 j 时的最大价值。

  • i 表示前 i 个物品。
  • j 表示当前背包的容量。

2. 状态转移方程​

对于每个物品 i，我们有两种选择：

  1. 不放入背包：此时背包的价值与之前相同，即 dp[i][j] = dp[i-1][j]。
  2. 放入背包：如果当前物品的重量 w[i] 不超过背包的容量 j，则背包的价值为 dp[i-1][j-w[i]] + v[i]。

因此，状态转移方程为：

plaintext
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

3. 初始化​

  • 当 i = 0 时，表示没有物品可选，因此 dp[0][j] = 0。
  • 当 j = 0 时，表示背包容量为 0，因此 dp[i][0] = 0。

4. 最终结果​

最终的结果存储在 dp[n][W] 中，表示前 n 个物品在背包容量为 W 时的最大价值。

代码示例​

以下是 Python 实现 0-1 背包问题的代码：

python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[n][capacity]

# 示例输入
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5

# 输出最大价值
print(knapsack(weights, values, capacity))  # 输出: 7

输入和输出​

  • 输入：

    • weights = [2, 3, 4, 5]：每个物品的重量。
    • values = [3, 4, 5, 6]：每个物品的价值。
    • capacity = 5：背包的容量。

  • 输出：

    • 7：在背包容量为 5 的情况下，能够获得的最大价值。

实际应用场景​

0-1 背包问题在现实生活中有许多应用场景，例如：

  1. 资源分配：在有限的预算下，如何选择最有价值的项目进行投资。
  2. 旅行打包：在行李箱容量有限的情况下，如何选择最有价值的物品携带。
  3. 任务调度：在有限的时间内，如何选择最有价值的任务来完成。

总结​

0-1 背包问题是动态规划中的经典问题，通过定义状态和状态转移方程，我们可以有效地解决这个问题。理解并掌握 0-1 背包问题的解法，不仅有助于提升编程能力，还能帮助我们更好地解决现实生活中的优化问题。

附加资源与练习​

  • 练习 1：尝试修改上述代码，使其能够输出选择的物品列表。
  • 练习 2：考虑如果物品可以部分放入背包（即分数背包问题），如何修改算法？
  • 推荐阅读：
    • 《算法导论》中的动态规划章节。
    • LeetCode 上的相关题目，如 0-1 Knapsack Problem。
提示

如果你对动态规划的其他问题感兴趣，可以继续学习“完全背包问题”和“多重背包问题”，它们都是 0-1 背包问题的变种。