工业实验提交.pdfVIP

实验三近似算法

一、实验目的

（1）掌握近似算法的基本设计思想与方法，

（2）掌握0/1背包问题近似算法的设计思想与方法，

（3）熟练使用高级编程语言实现近似算法，

（4）利用实验测试给出的近似算法的性能。

二、实验内容

1.实验问题

0/1背包问题：给定n种物品和一个背包，物品i的重量是wi，价值vi,背

包容量为C,问如何选择装入背包的物品，使装入背包中的物品的总价值最大？

对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。

2.实验要求

2.1实现基于动态规划方法的0/1背包算法

2.2实现一个0/1背包的近似算法。

2.3测试算法性能

实验测试在n=100、1000、10000情况，其中w、v和C均随机生成且物品

重量w和C随机生成的范围相同，都分别取范围（1-1000）、（1-100000）、

（1。对上述9种组合情况分别记录上述两种算法的运行时间，绘制

曲线。

-1-

三、实验过程及结果

1．整体设计

1.1问题分析

从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。

求使物品价值最高的。输入数据为：背包容量C，物品数量n，物品的

价值取值范围，物品质量的取值范围。需要根据范围随机生成每个物品的重量和

价值，最后给出得到的最大价值和物品是否放入背包的最优方案。

初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到

最优解，看以下实例：

贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用

这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值

最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑

n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时，获得的解为

x[1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。

贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种

规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考

虑n2,w=[10,20],p=[5,100],c25。当利用重量贪婪策略时，获得的解为

x=[1,0],比最优解[0,1]要差。

贪心准则3：价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选

择可装入包的pi/wi值最大的物品，但是这种策略也不能保证得到最优解。利用

此策略解n=3,w=[20,15,15],p=[40,25,25],c=30时的得到的就不是最优解。

由以上的三种贪心策略可知，本题如果采用贪心方法求解，则完全取决于输

入的数据，不管采用哪种方法都不能保证完全正确。

要使物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1=i=n，x取0或1，取1

表示选取物品i)取得最大值。在该问题中需要决定x1..xn的值。假设按i1，

2，...，n的次序来确定xi的值。如果置x10，则问题转变为相对于其余物品(即

物品2，3，.，n)，背包容量仍为c的背包问题。若置x11，问题就变为关于最

-2