数据结构与算法 / 系统课时

处理每种物品的数量上限

处理每种物品的数量上限

多重背包允许每类物品使用有限次,难点不是写出状态,而是把“最多取几件”正确放进转移。本篇先从枚举件数得到可靠基线,再用二进制拆分把数量约束转成若干零一物品,在保持结果不变的同时降低转移次数。

学习目标

  • 写出带数量上限的多重背包状态转移
  • 使用二进制拆分把一类物品转换为若干零一物品
  • 比较朴素枚举与二进制优化的时间复杂度和适用边界

从数量上限写出朴素转移

设背包容量为 C,第 i 类物品重量为 w、价值为 v,最多使用 s 件。令 dp[c] 表示处理完当前范围内的物品后,容量不超过 c 时能取得的最大价值。

处理这一类物品时,可以选择 0 到 s 件,但件数还不能让总重量超过当前容量。因此新状态满足:对每个容量 c,枚举 0≤k≤min⁡(s,⌊c/w⌋)0 \le k \le \min(s, \lfloor c / w \rfloor),候选值为旧状态 dp[c - k * w] + k * v。

这里必须从“处理该类物品之前”的状态读取。若一边枚举容量一边直接使用已经更新过的当前数组,就可能再次利用同一类物品,实际使用数量超过 s。最直接的做法是在处理每一类物品前保存一份 prev。

用二进制拆分减少枚举

当 s 很大时,逐个枚举 0...s 会成为主要开销。可以把数量 s 拆成 1, 2, 4, ... 的若干组,每组要么整体选择,要么不选择,于是每组都成为一个零一背包物品。

例如一类物品最多有 13 件,可以拆成 1 + 2 + 4 + 6。任意 0...13 的使用数量,都能由这些组中的若干组组合出来,因此数量约束没有丢失。每组的重量和价值分别乘以组内件数,然后按零一背包的容量倒序更新。

多重背包二进制拆分示意

对照实现与验证

下面用同一组输入分别执行朴素枚举和二进制拆分。物品使用 (重量, 价值, 数量上限) 表示,两个算法应得到完全相同的最优价值。

python
def bounded_knapsack_naive(items, capacity):
    dp = [0] * (capacity + 1)

    for weight, value, count in items:
        prev = dp[:]  # 固定上一阶段,防止当前类别被重复利用
        for c in range(capacity + 1):
            best = prev[c]
            max_count = min(count, c // weight)
            for k in range(1, max_count + 1):
                best = max(best, prev[c - k * weight] + k * value)
            dp[c] = best

    return dp[capacity]


def bounded_knapsack_binary(items, capacity):
    dp = [0] * (capacity + 1)

    for weight, value, count in items:
        group = 1
        remaining = count

        # 依次取 1、2、4...,最后一组接收剩余数量
        while remaining > 0:
            take = min(group, remaining)
            group_weight = weight * take
            group_value = value * take

            # 每个拆出的组只能使用一次,因此容量必须倒序更新
            for c in range(capacity, group_weight - 1, -1):
                dp[c] = max(dp[c], dp[c - group_weight] + group_value)

            remaining -= take
            group *= 2

    return dp[capacity]


items = [(3, 4, 3), (4, 5, 2)]
capacity = 10

print(bounded_knapsack_naive(items, capacity))
print(bounded_knapsack_binary(items, capacity))

预期输出

text
13
13

最优方案之一是选择两件重量为 3、价值为 4 的物品,再选择一件重量为 4、价值为 5 的物品,总重量正好为 10,总价值为 13。

比较复杂度与实现边界

朴素方法对每类物品、每个容量都可能继续枚举数量。如果第 i 类物品上限为 s_i,可以把时间复杂度理解为 O(C∑si)O(C \sum s_i);当所有上限都接近同一个 S 时,常写成 O(nCS)O(nCS)。空间复杂度为 O(C)O(C),额外复制的 prev 仍然是线性空间。

二进制拆分后,第 i 类物品只产生 O(log⁡(si+1))O(\log(s_i + 1)) 个零一物品,因此时间复杂度降为 O(C∑log⁡(si+1))O(C \sum \log(s_i + 1)),空间仍为 O(C)O(C)。数量上限较大时,这通常比逐件枚举稳定得多。

若某类物品的上限已经大到在容量范围内不可能用完,例如 count * weight >= capacity,它在当前容量下等价于完全背包,还可以进一步改用完全背包转移。面对有限数量约束时,先写对朴素转移,再根据上限规模选择二进制拆分,是最不容易出错的实现路径。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

处理每种物品的数量上限

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通