问题描述
有n种物品和一个容量为V的背包。第 i 种物品最多有m[i]件可用，每件价值是p[i]，体积是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法
这题目和完全背包问题很类似，只是多了一个限制条件。完全背包问题中，物品可以选择任意多件，只要你装得下，装多少件都行。但多重背包就不一样了，每种物品都有指定的数量限制。
基本的方程只需将完全背包问题的方程略微一改即可，因为对于第 i 种物品有m[i]+1种策略：取0件，取1件……取m[i]件。
令 f[i][j] 表示前 i 种物品恰放入一个容量为 j 的背包的最大权值，则有状态转移方程：
0<=k<=m[i] && 0 <= k * v[i] <= V：
f[i][j]=max{ f[i−1][j−k∗v[i]]+k∗p[i] }
递归解法：
-
常规解法：时间复杂度：
O(V∗Σm[i])
class Solution {
// 体积
let v:[Int] = [0,3,4,5]
// 价值
let p:[Int] = [0,2,3,4]
// 数量
let m:[Int] = [0,4,3,2]
func findMaxPrice(capital V: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: V + 1), count: v.count)
for i in 1..<v.count {
for j in v[i]...V {
var k = 0
while k * v[i] <= j && k <= m[i] {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i] * k] + p[i] * k)
k += 1
}
}
}
return dp[v.count - 1][V]
}
}
输出：11
-
转化为01背包问题
二进制拆分，将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。
例如意见物品的p[i]为13，就将这种物品拆分成系数分别为1,2,4,6的四件物品
这样就将第 i 种物品分成了O(log(p[i]))种物品，将原问题转化为了时间复杂度为O(V∗Σlog(m[i]))的01背包问题，是很大的改进。
class Solution {
// 体积
let v:[Int] = [0,3,4,5]
// 价值
let p:[Int] = [0,2,3,4]
// 数量
let m:[Int] = [0,4,3,2]
func findMaxPrice(capital V: Int) -> Int {
var dp = Array(repeating: 0, count: V + 1)
for i in 1..<v.count {
var num = min(m[i], V/v[i])
var k = 1
while num > 0 {
if k > num {
k = num
}
num -= k
//注意：这里使用了一维数组，因此 j 需要逆序循环
for j in ((v[i] * k)...V).reversed() {
dp[j] = max(dp[j], dp[j - v[i] * k] + p[i] * k)
}
k = k << 1
}
}
return dp[V]
}
}
3.O(VN)单调队列算法
原谅我太菜了，这个算法目前还是没太搞懂
这里附上网上的讲解
实际情况下二进制拆分已经够用，不会有人把时间卡到只能用单调队列优化，下面的优化看不懂的同学不要强求！
多重背包问题同样有 O(VN) 的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊 O(1) 的时间求解。代码如下（需要外套1...n1...n1...n循环）：
//p：某类物品数量，w：某类物品花费，v：某类物品价值，V:商品总价值
void MultiPack(int p, int w, int v) {
for (int j = 0; j < w; j++) { //j为w的所有组
int head = 1, tail = 0;
for (int k = j, i = 0; k <= V / 2; k += w, i++) {
int r = f[k] - i * v;
while (head <= tail and r >= q[tail].v) tail--;
q[++tail] = node(i, r);
while (q[head].id < i - p) head++; //需要的物品数目
f[k] = q[head].v + i * v;
}
}
}
这里原作者并没有作过多解释，代码也没有给，应要求在这里讲一下，是个人的之前理解
此前应先确保搞明白了单调队列，就是在区间移动时动态维护区间的最值
观察它的转移方程：f[i][j]=max(f[i−1][j],f[i−1][j−k∗w[i]]+k∗v[i])
单调队列优化的主要思想就是分组更新，因为w[i]是成倍增加的
f[i−1][j]只会更新f[i−1][j+k∗w[i]]f[i-1][j+k*w[i]]f[i−1][j+k∗w[i]]（这里是从前往后看的，所以是+）
对于当前为w的体积，我们可以按照余数将它分为w组，也就是0...w−10...w-10...w−1
同一个剩余系的数在一组
比如在模3意义下1,4,7,10是一组，2,5,8,11是一组，3,6,9,12是一组
每组的转移是互不影响的，也就是单独转移
举个例子
f[i][5w]=max(f[i−1][4w]+w,f[i−1][3w]+2v,f[i−1][2w]+3v,f[i−1][w]+4v,f[i−1][0]+5v)
f[i][4w]=max(f[i−1][3w]+w,f[i−1][2w]+2v,f[i−1][w]+3v,f[i−1][0]+4v)
让所有的f[i][j]都减去j/w∗v，式子就变成
f[i][5w]=max(f[i−1][4w]−4v,f[i−1][3w]−3v,f[i−1][2w]−2v,f[i−1][w]−v,f[i−1][0])
f[i][4w]=max(f[i−1][3w]−3v,f[i−1][2w]−2v,f[i−1][w]−v,f[i−1][0])
即f[i][j]=max(f[i−1][jmodw+k∗w]−k∗v+j∗v)
当j mod w一定后，就可以用单调队列来优化了
