背包问题

问题描述

给定一组物品，每种物品都有自己的重量和价值，背包的容量为 W，如何选择物品，使得背包中物品的总价值最大？

问题分析

这是一个典型的动态规划问题，我们可以用二维数组 dp[i][j] 表示前 i 个物品恰好装入一个容量为 j 的背包可以获得的最大价值。
v[i] 表示第 i 个物品的价值，w[i] 表示第 i 个物品的重量。

边界条件：dp[i][j] = 0，i=0 or j=0。

状态转移方程如下：

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

解释：

  • 如果不放第 i 个物品，那么前 i-1 个物品恰好装入一个容量为 j 的背包可以获得的最大价值是 dp[i-1][j]；
  • 如果放第 i 个物品，那么前 i-1 个物品恰好装入一个容量为 j-w[i] 的背包可以获得的最大价值是 dp[i-1][j-w[i]]，加上第 i 个物品的价值 v[i] 就是第 i 个物品恰好装入一个容量为 j 的背包可以获得的最大价值。

代码实现

1
2
3
4
5
6
7
8
9
10
def pachage_problem(W, w, v):
    n = len(w)#w是物品大小，v是物品价值，n是物品个数，W是背包的容量
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][W]

复杂度分析

时间复杂度：$O(nW)$，其中 n 是物品的个数，W 是背包的容量。

空间复杂度：$O(nW)$，需要创建一个 nW 大小的二维数组。

应用

  • 0-1 背包问题：给定一组物品，每种物品都有自己的价值，背包的容量为 W，如何选择物品，使得背包中物品的总价值最大？
  • 完全背包问题：给定一组物品，每种物品都有自己的价值和容量，如何选择物品，使得背包中物品的总价值最大？
  • 多重背包问题：给定 n 件物品，每件物品都有自己的价值和容量，以及 m 个背包，如何选择物品，使得每个背包中物品的总价值最大？

扩展

完全背包问题

每种物品的数量是无限的，完全背包其实可以转换成0/1背包，第i种物品的出现次数至多是背包容量m/物品i重量w[i]。

多重背包问题

直接转换为0-1背包问题效率较低，为了优化，可以使用二进制分解的技巧，将每个物品的数量k[i]分解成若干份。二进制分解的优势在于它可以将原本k[i]的复杂度从$O(k[i])$降低到$O(log(k[i]))$。具体方法是将k[i]进行二进制拆分，比如k[i] = 13，可以拆分成1, 2, 4, 6，使复杂度降低。