博客

部分背包问题是背包问题的一种变形，同样属于经典的动态规划问题。在部分背包问题中，物品有数量限制，可以选择一部分放入背包中，而且每个物品的重量和价值也不同。目标是必须选择一些物品放入背包中，使得在满足背包最大重量限制下，背包中物品的总价值最大。

解法

与经典背包问题类似，部分背包问题也可以使用动态规划来解决。但是与经典背包问题不同的是，部分背包问题中每个物品的数量是有限制的，因此我们需要改变动态规划的状态表示。

假设背包的最大重量为W，有n个物品，其中第i个物品的重量为w[i]，价值为v[i]，数量为s[i]。设f[j]表示当背包容量为j时所能获得的最大价值。则状态转移方程为：

f[j] = max{f[j – w[i]] + v[i] | 0 <= k <= s[i], j >= k * w[i]}

其中max表示选取最大值，本式的含义是：当背包容量为j时，最大价值可能有多种情况。一种情况是不放置任何第i个物品，即f[j] = f[j]，这种情况在前面已经被考虑过了。另一种情况是放置k个第i个物品，即f[j] = f[j – k * w[i]] + k * v[i]，这种情况需要在k的取值范围内枚举并选取最大值。

因为在状态转移方程中需要枚举k次，因此时间复杂度为 $O(nW \sum s[i])$，其中$W$为背包的最大承重。

示例

示例一

假设我们有一个背包，最大承重为12，有下列物品：

则部分背包问题可以用下面的状态转移方程解决：

def knapsack(v, w, s, c):
    f = [0] * (c + 1)
    n = len(v)
    for i in range(n):
        for k in range(1, s[i] + 1):
            for j in range(c, k * w[i] - 1, -1):
                f[j] = max(f[j], f[j - k * w[i]] + k * v[i])
    return f[-1]

程序输出为：

>>> knapsack([6, 10, 12, 8], [2, 5, 7, 4], [1, 2, 1, 3], 12)
84

表明背包最大价值为84。

示例二

假设我们有一个背包，最大承重为10，有下列物品：

则部分背包问题可以用下面的状态转移方程解决：

def knapsack(v, w, s, c):
    f = [0] * (c + 1)
    n = len(v)
    for i in range(n):
        for k in range(1, s[i] + 1):
            for j in range(c, k * w[i] - 1, -1):
                f[j] = max(f[j], f[j - k * w[i]] + k * v[i])
    return f[-1]

程序输出为：

>>> knapsack([6, 10, 12, 8], [2, 5, 7, 4], [1, 2, 1, 3], 10)
72

表明背包最大价值为72。