有一个容量为 n 的背包和 m+1 种物品，每种物品都有无限多个。 物品种类编号为 0∼m 。 第 i 种物品的体积为 vi ，价值为 wi 。 在使用背包装入物品时，每种物品的限重如下： 第 0 种物品：重量忽略不计，在装入时没有重量限制。 第 1∼m 种物品：第 i 种物品的单个重量为 hi ，如果该种物品的装入总重量超过 li ，则视为超重。 现在，请你挑选物品装入背包，要求 所有装入物品的总体积不得超过背包容量。 所有存在重量限制的物品均不得超重。 满足以上所有条件的前提下，所有装入物品的总价值尽可能大。 输出总价值的最大可能值。 注意审题，不要将 n,m 的含义弄混。 输入格式 第一行包含四个整数 n,m,v0,w0 。 接下来 m 行，每行包含四个整数 li,hi,vi,wi 。 输出格式 一个整数，表示总价值的最大可能值。

算法1

(多重背包+二进制优化)

对于第 0 种物品，可以按照普通的多重背包来处理，但是对于第 1~m 种物品，由于有重量限制，直接使用多重背包的实现效率比较低，因为 1~m 种物品的数量不确定，所以需要二进制优化。具体来说，对于第 i 种物品，将其拆分成若干个物品，每个物品的重量都是 hi 的若干倍（即可以装入 hi 的1~k 倍），价值也与数量有关，最后使用多重背包来求解即可。

时间复杂度

最坏情况下，需要处理的物品总数为 O(mlog l) ，单次多重背包的时间复杂度为 O(nlog v)，总时间复杂度为 O(nmlog vlog l)

C++ 代码

算法2

(多重背包+单调队列优化)

C++ 代码

相关问题

用python实现有一个容量为 n 的背包和 m+1 种物品，每种物品都有无限多个。 物品种类编号为 0∼m 。 第 i 种物品的体积为 vi ，价值为 wi 。 在使用背包装入物品时，每种物品的限重如下： 第 0 种物品：重量忽略不计，在装入时没有重量限制。 第 1∼m 种物品：第 i 种物品的单个重量为 hi ，如果该种物品的装入总重量超过 li ，则视为超重。 现在，请你挑选物品装入背包，要求 所有装入物品的总体积不得超过背包容量。 所有存在重量限制的物品均不得超重。 满足以上所有条件的前提下，所有装入物品的总价值尽可能大。 输出总价值的最大可能值。 注意审题，不要将 n,m 的含义弄混。 输入格式 第一行包含四个整数 n,m,v0,w0 。 接下来 m 行，每行包含四个整数 li,hi,vi,wi 。 输出格式 一个整数，表示总价值的最大可能值。 数据范围 前 4 个测试点满足 1≤n≤100 ，1≤m≤2 。 所有测试点满足 1≤n≤1000 ，1≤m≤10 ，1≤li,hi,vi,wi≤100 。 输入样例1： 10 2 2 1 7 3 2 100 12 3 1 10 输出样例1： 241 输入样例2： 100 1 25 50 15 5 20 10 输出样例2： 200

思路：多维度背包问题，需要引入三维f[w1][w2][j]表示当容量为w1时钦定第一件物品，容量为w2时不钦定任何一件重量超过限重的物品，前j种物品的最大价值。 不钦定物品可以理解为钦定该物品贡献为0，这样写可以允许特判j=0的情况。 由于加入了一个物品是有良序性的（即加入后可能导致第二个物品超重），所以要在体积一样的时候，对当前物品加入、不加入、减去若干件物品重量后再加入三种选择相对于容积/重量限的判断。时间复杂度O(n^3*m)

python 代码：

1268：【例9.12】完全背包问题 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 32325 通过数: 17348 【题目描述】 设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M ，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M ，而价值的和为最大。 【输入】 第一行：两个整数，M (背包容量，M≤200 )和N (物品数量，N≤30 )； 第2..N+1 行：每行二个整数Wi,Ci ，表示每个物品的重量和价值。 【输出】 仅一行，一个数，表示最大总价值。 【输入样例】 10 4 2 1 3 3 4 5 7 9 【输出样例】 max=12

题意描述

有 $n$ 种物品，每种物品有一个重量 $w_i$ 和价值 $v_i$，数量不限。将它们装入重量为 $M$ 的背包，使得背包内物品的总价值最大。输出该最大总价值。

分析

完全背包问题，可使用 DP 解决，无法使用贪心策略。DP 状态定义为 $f(i,j)$：考虑前 $i$ 件物品，背包容量为 $j$ 时所能获得的最大价值。

考虑 $w_i \le j$ 时，可以将第 $i$ 种物品放入背包。则有 $f(i,j) = f(i,j-w_i)+v_i$。

否则，无法将此物品放入背包，因此最优策略是不选第 $i$ 种物品。则有 $f(i,j) = f(i-1,j)$。

最终答案为 $\max\limits_{j=0}^M f(n,j)$。

在 DP 中，循环枚举的顺序很重要。在完全背包问题中，每件物品可以无限次选取，因此对于每一种物品 $i$，我们应当考虑选取 $0, 1, 2, \ldots, \lfloor \frac{M}{w_i} \rfloor$ 件物品。因此枚举顺序为：先枚举物品，再枚举背包容量。

具体实现中，每种物品的枚举应当采用倒序，即从大到小枚举，这样可以避免多次使用某件物品。

代码实现

代码实现非常简单，只需根据状态转移方程填写 DP 数组即可，时间复杂度为 $O(NM)$。