if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n个物品的重量和} if k<=n then begin

if v>w[k] then search(k+1,v-w[k]); search(k+1,v); end; end; l DP

F[i,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。 实现:

A:将最优化问题转化为判定性问题

f [i, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true. For I:=1 to n do

For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]]; 优化：当前状态只与前一阶段状态有关，可降至一维。 F[0]:=true;

For I:=1 to n do begin F1:=f;

For j:=w[I] to v do

If f[j-w[I]] then f1[j]:=true; F:=f1; End;

B:求可以放入的最大价值。

F[I,j] 为容量为I时取前j个背包所能获得的最大价值。

F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] } C:求恰好装满的情况数。 DP:

Procedure update;

18

var j,k:integer; begin c:=a;

for j:=0 to n do if a[j]>0 then

if j+now<=n then inc(c[j+now],a[j]); a:=c; end[9];

19

3 解0-1背包问题的算法比较与分析

这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过对O-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算法可读性要优于前者。

动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝,常用的分枝一限界法有最小耗费法，最大收益法。FIFO(先进先出)法等。0-1背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要O(2n)的解空间。故该算法不常用在背包问题求解。遗传算法是计算数学中用于解决最优化的搜索算法，是一种进化算法。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。通常解用二进制0和1表示，进化从一个个体发生，然后一代一代发生。在每一代中，该种群的价值被评估，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择。

回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0(解空间的最大路径长度)，而分枝限界所占用的内存为0(解空间大小)。对于一个子集空间，回溯法需要0(n)的内存空间，而分枝限界则需要0(2n)的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。

为了更直观更有效地分析动态规划法回溯法两种算法，下面分别对它们的计算时间进行测试。测试中,每个0-1 背包问题的效益和重量分别为随机产生的两组数据,其取值范围为[0,999],背包容量定为1125。为便于各算法间进行比较，测试之前首先把物品按价值重量比的非增顺序排序。每次测试将程序运行100

20

次所得时间为运行 100次的平均值。测试结果如下表所示[18]。

问题规模 5 10 15 20 25 50 100 200 平均计算时间 动态规划法 0.003112 0.009370 0.012550 0.015150 0.017180 0.026460 0.041870 0.072550 回溯法 0.003817 0.009630 0.013120 0.015780 0.018900 0.026710 0.039840 0.058430 从表中的测试结果可以看出 当问题规模较小时，三种方法都有较好的稳定性，计算时间都相差不多。随着问题规模的增大，各算法的计算时间都在增大， 其中递归法的计算时间增长速度最快，当问题规模为50，100和200时，其计算时间太长以致失去利用该法求解的意义，而动态规划法与回溯法则相对稳定且计算时间也相差不多，但是当问题规模大到一定程度，回溯法要优于动态规划法。

通过以上对0-1背包问题的求解分析，我们可以看到各种算法设计方法有各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解0-1背包问题，各算法的时问复杂度、优缺点以及改进方法的比较如下表所示[19]:

动态规划 O(min{nc,2n}） 可求得最优决策序列 建立动态规划递归方程 判断右子树能够获得最优时间复杂度较时，按效率密解 高 度vi/wi对剩余对象排序 最大收益或最速度较快，易占用的内存较小消耗分枝-求解 大，效率不高 限界法，FIFO法 能够解决传统基于惩罚函数算法不能解决速度较慢，算修正方法和译的问题，能够法不成熟 码方法 获得最优解 速度较慢 回溯法 O(n2n） 分枝-限界法 O(2n） 遗传算法 O(n2n）

21