背包问题的算法研究与实现本科毕业论文 精品

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

联系客服:779662525#qq.com(#替换为@)