博客

部分背包问题是经典的01背包问题的扩展，与01背包问题不同的是，在部分背包问题中每个物品的数量并不是固定的1个，而是可以是任意正整数。

1. 问题描述：

有一个容量为C的背包，有n个物品，第i个物品的重量为w[i]，价值为v[i]，数量为s[i]。问该背包最多能装下多少价值的物品。

1. 算法思路：

部分背包问题可以转化为多重背包问题求解，将每个物品i拆分为s[i]件相同的物品，便形成了一个有s[i]个物品i的多重背包问题。对每个拆分后的物品i，重量为w[i]，价值为v[i]。接下来，我们就可以用多重背包问题的思路去求解。

具体的实现方式有两种：一种是直接基于多重背包问题的常规DP算法进行求解；另一种是“优化建图”的方式，将多重背包问题转化成01背包问题求解，这种方式可以大幅减少DP的时间复杂度，性能更加优异。

1. 代码实现：

先介绍基于多重背包问题的常规DP算法实现：

def multi_knapsack(c, w, v, s):
    """
    c: 背包容量
    w: 物品重量列表
    v: 物品价值列表
    s: 物品数量列表
    """
    # 初始化dp数组
    dp = [0] * (c + 1)
    # 遍历每个物品
    for i in range(len(w)):
        # 如果当前物品数量为0，则跳过
        if s[i] == 0:
            continue
        # 多重背包问题的DP过程
        for j in range(c, 0, -1):
            for k in range(1, s[i] + 1):
                if j >= k * w[i]:
                    dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])
                else:
                    break
    # 返回dp数组的最后一个元素
    return dp[-1]

再介绍一种“优化建图”的方式实现：

def optimized_multi_knapsack(c, w, v, s):
    """
    c: 背包容量
    w: 物品重量列表
    v: 物品价值列表
    s: 物品数量列表
    """
    # 初始化dp数组
    dp = [0] * (c + 1)
    # 遍历每个物品
    for i in range(len(w)):
        # 如果当前物品数量为0，则跳过
        if s[i] == 0:
            continue
        # 将多重背包问题转化为01背包问题
        t = 1
        while t < s[i]:
            for j in range(c, t * w[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - t * w[i]] + t * v[i])
            s[i] -= t
            t *= 2
        if s[i] > 0:
            for j in range(c, s[i] * w[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - s[i] * w[i]] + s[i] * v[i])
    # 返回dp数组的最后一个元素
    return dp[-1]

1. 示例说明：

假设有如下背包问题：

容量为10，物品有5个，分别为：

使用上面所介绍的两个函数，计算该背包问题的最大价值：

c = 10
w = [6, 4, 3, 5, 2]
v = [20, 15, 10, 8, 4]
s = [3, 2, 5, 1, 10]

print("基于多重背包问题的常规DP算法实现，最大价值为：", multi_knapsack(c, w, v, s))
print("基于\"优化建图\"的方式实现，最大价值为：", optimized_multi_knapsack(c, w, v, s))

输出结果为：

基于多重背包问题的常规DP算法实现，最大价值为： 135
基于"优化建图"的方式实现，最大价值为： 135

通过测试结果可以看出，在本例中两种实现方式的结果都是一样的，因此二者的正确性是等价的。