其中的 F [v] ← Kt{F [v],F[v − C
i
]+W
i
} 一句,恰就对应于我们原来的转移方程,因
为现在的 F [v − C
i
] 就相当于原来的 F [i − 1,v− C
i
]。如果将 v 的循环顺序从上面的逆
序改成顺序的话,那么则成了 F [i, v] 由 F [ i, v − C
i
] 推导得到,与本题意不符。
事实上,使用一维数组解 yR 背包的程序在后面会被多次用到,所以这里抽象出一
个处理一件 yR 背包中的物品过程,以后的代码中直接调用不加说明。
/27 w2`QPM2S+FUF, C, WV
7Q` v ← V iQ C
F [v] ← Kt(F [v],F[v − C]+W )
有了这个过程以后,yR 背包问题的伪代码就可以这样写:
F [0..V ] ←0
7Q` i ← 1 iQ N
w2`QPM2S+FUF, C
i
,W
i
V
RX9 初始化的细节问题
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目
要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别
这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法,要求恰好装满背包,那么在初始化时除了 F [ 0] 为 0,其它
F [1..V ] 均设为 −∞,这样就可以保证最终得到的 F [V ] 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 F [0..V ]
全部设为 0。
这是为什么呢?可以这样理解:初始化的 F 数组事实上就是在没有任何物品可以放
入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可以在什
么也不装且价值为 0 的情况下被“恰好装满”,其它容量的背包均没有合法的解,属于
未定义的状态,应该被赋值为 @ũ 了。如果背包并非必须被装满,那么任何容量的背包
都有一个合法解“什么都不装”,这个解的价值为 0,所以初始时状态的值也就全部为 0
了。
这个小技巧完全可以推广到其它类型的背包问题,后面不再对进行状态转移之前的
初始化进行讲解。
RX8 一个常数优化
上面伪代码中的
7Q` i ← 1 iQ N
7Q` v ← V iQ C
i
中第二重循环的下限可以改进。它可以被优化为
7Q` i ← 1 iQ N
7Q` v ← V iQ Kt(V − Σ
N
i
W
i
,C
i
)
这个优化之所以成立的原因请读者自己思考。(提示:使用二维的转移方程思考较易。)
9