多重背包

What · 是什么

多重背包是0-1背包的变式：每种物品有有限数量 k_i 个而非仅一个。朴素做法将每种物品拆成 k_i 个独立物品做0-1背包(O(W*sum k_i))；二进制分组优化将 k_i 拆成 1+2+4+...+余数 的二进制组(O(W*sum log k_i))；单调队列优化可进一步降至O(nW)。

Why · 为什么

How · 实现

伪代码

# 二进制分组优化
items = []  # (weight, value) 拆分后的0-1背包物品
for i in 1..n:
  c = 1
  while c < k[i]:
    items.append((c*w[i], c*v[i]))
    k[i] -= c; c *= 2
  items.append((k[i]*w[i], k[i]*v[i]))
# 标准0-1背包
for item in items:
  for j in W down to item.weight:
    f[j] = max(f[j], f[j-item.weight] + item.value)

Python 实现

def multiple_knapsack(W, weights, values, counts):
    """多重背包(二进制分组优化)
    W: 背包容量
    weights: [w1, w2, ...] 各物品重量
    values: [v1, v2, ...] 各物品价值
    counts: [k1, k2, ...] 各物品数量
    返回: 最大价值
    """
    n = len(weights)
    f = [0] * (W + 1)

    for i in range(n):
        w, v, k = weights[i], values[i], counts[i]
        # 二进制分组拆分
        c = 1
        while c < k:
            bw, bv = c * w, c * v
            for j in range(W, bw - 1, -1):
                if f[j - bw] + bv > f[j]:
                    f[j] = f[j - bw] + bv
            k -= c
            c <<= 1
        # 剩余部分
        if k > 0:
            bw, bv = k * w, k * v
            for j in range(W, bw - 1, -1):
                if f[j - bw] + bv > f[j]:
                    f[j] = f[j - bw] + bv

    return f[W]


def multiple_knapsack_naive(W, weights, values, counts):
    """多重背包(朴素三重循环, 用于验证)"""
    n = len(weights)
    f = [0] * (W + 1)
    for i in range(n):
        w, v, k = weights[i], values[i], counts[i]
        for j in range(W, w - 1, -1):
            for c in range(1, k + 1):
                if c * w <= j and f[j - c * w] + c * v > f[j]:
                    f[j] = f[j - c * w] + c * v
    return f[W]


if __name__ == "__main__":
    # 测试: 容量10, 物品[(w=2,v=3,k=4),(w=3,v=2,k=2),(w=4,v=5,k=1)]
    W = 10
    w = [2, 3, 4]
    v = [3, 2, 5]
    k = [4, 2, 1]

    ans = multiple_knapsack(W, w, v, k)
    ans_naive = multiple_knapsack_naive(W, w, v, k)
    assert ans == ans_naive, f"Binary={ans}, Naive={ans_naive}"
    # 最优: 取4个物品0(重8值12) + 1个物品2不可(重8+4>10)
    # 或: 3个物品0(重6值9)+1个物品2(重4值5)=重10值14
    assert ans == 14, f"Expected 14, got {ans}"

    # 边界测试
    assert multiple_knapsack(0, [1], [1], [1]) == 0
    assert multiple_knapsack(5, [3], [10], [1]) == 10

    print("All tests passed.")

易错点

• 二进制拆分时余数处理：c < k 时继续拆，最后剩余 k 作为一组，不是 c <= k
• 拆分后的捆绑物品做0-1背包时容量必须倒序枚举(避免同一捆绑组内多次取)
• 单调队列优化时余数分组，同余数类内维护滑动窗口最大值
• k_i=0的物品应跳过，不要加入拆分

例题

信源

• OI Wiki✓ https://oi-wiki.org/dp/knapsack/
• CP-Algorithms✓ https://cp-algorithms.com/dynamic_programming/knapsack.html