多重背包问题的朴素做法中:
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
// 第 i 种物品取 k 个,k * v[i] 必须要小于等于 j 才能选
for (int k = 0; k * v[i] <= j; k ++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
k 层循环最坏情况下药循环 j 次,因此整体的时间复杂度为 O(nmˆ2)
,当 n 和 m 都是 10ˆ3 的数量级时就会 超时。
多重背包问题的状态转移方程:f(i, j) = max(f(i - 1, j - s * v[i]) + s * w[i])
完全背包问题的状态转移方程:f(i, j) = max(f(i - 1, j - k * v[i]) + k * w[i])
可以发现,两种问题的状态转移方程非常相似,那么是否能通过完全背包问题的优化思路,来优化多重背包问题呢?我们可以先按照之前的逻辑,展开多重背包问题的状态转移方程:
再展开完全背包问题的状态转移方程:
完全背包问题中,f(i, j - v) + w
能代入 f(i, j)
中,将表达式优化为 f(i, j) = max(f(i, j - v[i]) + w[i])
的原因是,每一种物品 i 可以取 无限个,所以理论上当 j 趋近于 +∞ 时,k 也可以取到 +∞,因此取极限可以将 f(i, j - v) + w
能代入 f(i, j)
。
而多重背包问题中,每种物品 i 的数量是确定的 s,所以 f(i, j - v) + w
展开后比 f(i, j)
多了一项 f(i-1, j-(s+1)v+(s+1)w
,在求集合最值的操作中,不能将集合中的某一项移动到等式左边,所以多重背包问题不能像完全背包问题那样优化,f(i, j - v) + w
不能被代入 f(i, j)
。
如何优化
问题的核心是运算数量级太大会超时,所以我们可以考虑将循环次数降级。
每种物品有 s 个,所以需要枚举 s 种情况,但我们不需要每一次都遍历,可以将 s 分组打包。
比如:s = 1023 时,不需要枚举 0, 1, 2, … 1023,按照 2^k 分组
当 k = 0 时,2^0 = 1,可以列举 s = 0~1
当 k = 1 时,2^1 = 2,可以列举 s(0) + 2 = 2~3 ,加上 s(0) 就是 0~3
当 k = 2 时,2^2 = 4,可以列举 s(1) + 4 = 4~7,加上 s(1) 就是 0~7
当 k = 3 时,2^3 = 8,可以列举 s(2) + 8 = 8~15,加上 s(2) 就是 0~15
…
即如果把 s 按照 2^k 分组,定能组合出 0 ~ 2^k - 1 之间的任何数。
特殊的例如 s = 200 时,按照幂分组:
k = 0(1),1(2),2(4),3(8),4(16),5(32),6(64),7(128),8(256)
如果 k = 8,组合出的数会超过 s = 200,此时不能取该值。
如果 k = 7,则可以推出 0 ~ 127 之间的任何数,所以需要补一个数 c 来满足凑齐 73 ~ 200 之间的数,按照之前的推理,该数 c = s - 2ˆk - 1
,k 为 2^k < s
的最大指数。
对于分组打包好的物品需要重新计算体积 v 和价值 w。
cnt 代表的是当前分组的数量,即 2ˆ0, 2ˆ1, 2ˆ2, .., 2ˆk, s - 2ˆk - 1
v 代表的是打包分组后,第 i 组的物品总体积:v[k] = cnt * v[i]
w 代表都是打包分组后,第 i 组的物品总价值:w[k] = cnt * w[i]
而对这 k 组物品物品则可以使用 01背包 的思想,即第 k 组物品要还是不要,来进行状态计算。
所以优化后的状态转移表达式为:f(i, j) = max(f(i - 1, j), f(i - 1, j - v[k]) + w[k])
。
计算过程
二进制优化版代码
import java.util.*;
import java.io.*;
public class Main {
// N = N * logS = 110 * log100 ≈ 710
static int N = 710;
static int[] v = new int[N];
static int[] w = new int[N];
static int[] f = new int[M];
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
int m = sc.nextInt();
// 打包分组下标
int k = 0;
// 对每一种物品进行分组打包,
for (int i = 1; i <= n; i ++) {
// 第 i 种物品信息(体积,价值,数量)
int vi = sc.nextInt();
int wi = sc.nextInt();
int s = sc.nextInt();
// 打包分组的数量
int cnt = 1;
// 只要可分组数量还未超过 s,就按照 2^k 打包
while (cnt <= s) {
k ++;
// 分组物品的体积 = 当前分组数量 * 物品体积
v[k] = cnt * vi;
// 分组物品价值 = 当前分组数量 * 物品价值
w[k] = cnt * wi;
// 当前物品数量 - 已分组的物品数量
s -= cnt;
// 分组数量 * 2
cnt *= 2;
}
// 如果可分组数量 cnt < s,并且 s > 0,说明有剩余物品未打包,需要再次打包
if (s > 0) {
k ++;
v[k] = s * vi;
w[k] = s * wi;
}
}
// 对每一个分组进行01背包求解
for (int i = 1; i <= k; i ++) {
for (int j = m; j >= v[i]; j --) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
sc.close();
}
}