带物品数量限制的0-1背包问题求解及代码修改咨询

现有商店物品列表，每个物品以[w_i, v_i, c_i]形式表示（w_i为重量，v_i为价值，c_i为可用数量），背包承重不超过W。需确定选择各物品的数量以获取最大价值。这是0-1背包问题的变体，已有传统0-1背包求解代码，咨询如何修改该代码解决此问题。传统代码如下：

n=len(val)
table = [[0 for x in range(W + 1)] for x in range(n + 1)] 

for i in range(n + 1): 
    for j in range(W + 1): 
        if i == 0 or j == 0: 
            table[i][j] = 0
        elif wt[i-1] <= j: 
            table[i][j] = max(val[i-1] + table[i-1][j-wt[i-1]], table[i-1][j]) 
        else: 
            table[i][j] = table[i-1][j] 

return table[n][W]  

这个问题是多重背包问题，和0-1背包的核心区别是每个物品可选取0到c_i次（而非仅0或1次）。下面提供两种修改思路，对应不同场景：

方法一：二进制拆分优化（高效，适合物品数量多/单次数量大的场景） #

把每个多重物品拆分成若干个「虚拟0-1物品」，直接复用原0-1背包的逻辑。拆分规则是将物品数量c_i拆成若干个二进制数的组合，这些组合可以覆盖0到c_i的所有选取次数。比如c_i=5，拆成1、2、2（1+2+2=5），通过选择不同虚拟物品的组合，就能实现选0、1、2、3、4、5个原物品的效果。

修改步骤： #

1. 拆分原物品列表，生成新的重量列表new_wt和价值列表new_val
2. 将拆分后的列表传入原0-1背包代码求解

示例代码： #

def multiple_knapsack(wt, val, cnt, W):
    # 二进制拆分物品
    new_wt = []
    new_val = []
    for w, v, c in zip(wt, val, cnt):
        k = 1
        while k <= c:
            new_wt.append(w * k)
            new_val.append(v * k)
            c -= k
            k *= 2
        if c > 0:
            new_wt.append(w * c)
            new_val.append(v * c)
    # 复用原0-1背包代码
    n = len(new_val)
    table = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                table[i][j] = 0
            elif new_wt[i-1] <= j:
                table[i][j] = max(new_val[i-1] + table[i-1][j - new_wt[i-1]], table[i-1][j])
            else:
                table[i][j] = table[i-1][j]
    return table[n][W]

方法二：直接修改状态转移方程（简单直观，适合物品数量少/单次数量小的场景） #

针对每个物品，遍历所有可能的选取数量（0到min(c_i, j//w_i)），在状态转移时取所有情况的最大值。

修改后的代码： #

def multiple_knapsack(wt, val, cnt, W):
    n = len(val)
    table = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                table[i][j] = 0
            else:
                # 不选当前物品的初始最大值
                max_val = table[i-1][j]
                # 尝试选1到最大可选数量的当前物品
                max_k = min(cnt[i-1], j // wt[i-1])
                for k in range(1, max_k + 1):
                    current_val = val[i-1] * k + table[i-1][j - wt[i-1] * k]
                    if current_val > max_val:
                        max_val = current_val
                table[i][j] = max_val
    return table[n][W]

代码说明： #

原0-1背包仅比较「选1个」和「不选」两种情况，这里扩展为比较「选0个、1个...直到最大可选数量」的所有情况。当物品可用数量c_i较大时，嵌套循环会显著增加时间复杂度，此时更推荐方法一。

内容的提问来源于stack exchange，提问作者Shakil Ahmed Sumon