的 f(i, cw),当再次计算到重复的 f(i, cw) 的时候,可以直接从备忘录中取出来用,就不用
再递归计算了,这样就可以避免冗余计算。
这种解决方法非常好。实际上,它已经跟动态规划的执行效率基本上没有差别。但是,多一
种方法就多一种解决思路,我们现在来看看动态规划是怎么做的。
我们把整个求解过程分为 n 个阶段,每个阶段会决策一个物品是否放到背包中。每个物品
决策(放入或者不放入背包)完之后,背包中的物品的重量会有多种情况,也就是说,会达
到多种不同的状态,对应到递归树中,就是有很多不同的节点。
我们把每一层重复的状态(节点)合并,只记录不同的状态,然后基于上一层的状态集合,
来推导下一层的状态集合。我们可以通过合并每一层重复的状态,这样就保证每一层不同状
态的个数都不会超过 w 个(w 表示背包的承载重量),也就是例子中的 9。于是,我们就
成功避免了每层状态个数的指数级增长。
我们用一个二维数组 states[n][w+1],来记录每层可以达到的不同状态。
第 0 个(下标从 0 开始编号)物品的重量是 2,要么装入背包,要么不装入背包,决策完
之后,会对应背包的两种状态,背包中物品的总重量是 0 或者 2。我们用 states[0]
[0]=true 和 states[0][2]=true 来表示这两种状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
private int[] weight = {2,2,4,6,3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录,默认值 false
public void f(int i, int cw) { // 调用 f(0, 0)
if (cw == w || i == n) { // cw==w 表示装满了,i==n 表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
}
if (mem[i][cw]) return; // 重复状态
mem[i][cw] = true; // 记录 (i, cw) 这个状态
f(i+1, cw); // 选择不装第 i 个物品
if (cw + weight[i] <= w) {
f(i+1,cw + weight[i]); // 选择装第 i 个物品
}
}