如何通过二进制优化解决多重背包问题中的动态规划问题？

本文共计2083个文字，预计阅读时间需要9分钟。

回顾在上一讲中，我们提到，多重背包问题似乎无法像完整背包那样解决。通过使用一维空间优化，我们可以降低时间复杂度。同时，对多重背包中的物品进行扁平化，可以将多个相同物品合并成01背包问题中的单个物品。

回顾

在 ​​上一讲​​ 中我们说到，多重背包问题无法像完全背包那样，通过一维空间优化来降低时间复杂度。

同时，对多重背包中的物品进行「扁平化」，可以彻底转换成 01 背包问题。

但由于处理的物品没有变少，因此枚举的情况也不会变少，时间复杂度也不会发生改变，反而增加了扁平化的成本，使得算法的常数变大。

我们目前学的多重背包在各维度数量级同阶的情况下，时间复杂度为 ，只能解决 数量级的问题。

题目描述

有 种物品和一个容量为 的背包，每种物品「数量有限」。

第 件物品的体积是 ，价值是 ，数量为 。

问选择哪些物品，每件物品选择多少件，可使得总价值最大。

其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择「有限次数」的特点（在容量允许的情况下）。

示例 1：

输入: N = 2, C = 5, v = [1,2], w = [1,2], s = [2,1]

输出: 4

解释: 选两件物品 1，再选一件物品 2，可使价值最大。