计算机算法分析与设计论文 背包问题的算法设计策略对比与分析

1、算法设计与分析课程考查论文背包问题的算法设计策略对比与分析0-1背包问题的算法设计策略对比与分析0 引言对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使

2、用自然语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序，可见算法在计算机科学界与计算机应用界的地位。1 算法复杂性分析的方法介绍算法的复杂性是算法效率

3、的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚：用

4、怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。让我们从比较两对具体算法的效率开始。1.1比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得Ai=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足Ai=c；或者扫到A的最后一个分量，经检测仍不满足Ai=c。我们用一个函数Search来表达这个算法：Function Search (c:integer):integer;V

5、ar J:integer; BeginJ:=1; 初始化在还没有到达A的最后一个分量且等于c的分量还没有找到时，查找下一个分量并且进行检测 While (Ai<c)and(j<m) do          j:=j+1; If Aj=c then search:=j 在数组A中找到等于c的分量，且此分量的下标为j else Search:=0; 在数组中找不到等于c的分量End;容易看出，在最坏的情况下，这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。解决问题1的另一个算法利用到已知条件

6、中A已排好序的性质。它首先拿A的中间分量Am/2与c比较，如果Am/2=c则解已找到。如果Am/2>c，则c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中继续查找；如果Am/2<c，则c只可能在Am/2+1,Am/2+2,.,Am之中，因而下一步只要在Am/2+1,Am/2+2,.,Am中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得Ai=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种

7、情况则找不到。这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达：Function B_Search ( c: integer):integer;VarL,U,I：integer;U和L分别是要查找的数组的下标的上界和下界Found：boolean;BeginL:=1; U:=m; 初始化数组下标的上下界Found:=false; 当前要查找的范围是AL.AU。当等于c的分量还没有找到且U>=L时，继续查找While (not Found) and (U>=L) doBeginI:=(U+L) div

8、2;找数组的中间分量If c=AI then Found:=Tureelse if c>AI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1else B_Search:=0;End;容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说

9、明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（m>m0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度

10、。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。1.2复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元

11、函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为T =T(N,I)和 S =S(N,I)由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以下文将主要地讨论时间复杂性。下面以T(N,I)为例，将复杂性函数具体化。根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2 ,.,Ok；再设这些元运算每执行一次所需要的时间

12、分别为t1,t2,.,tk 。对于给定的算法A，设经过统计，用到元运算Oi的次数为ei，i=1,2,.,k ，很明显，对于每一个i，1<=i<=k，ei是N和I的函数，即ei=ei(N,I)。那么有：(2.3)其中ti，i=1,2,.,k,是与N,I无关的常数。显然，我们不可能对规模N的每一种合法的输入I都去统计ei(N,I),i=1,2,k。因此T(N,I)的表达式还得进一步简化，或者说，我们只能在规模为N的某些或某类有代表性的合法输入中统计相应的ei , i=1,2,k，评价时间复杂性。下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax

13、(N )、Tmin(N)和Tavg(N )。在数学上有：(2.4)(2.5)(2.6)其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入，是DN中一个使T(N,)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(

14、N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。1.3复杂性的渐近性态及其阶随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、

15、结构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于时,T(N)也将单调增加趋于。对于T(N)，如果存在T(N)，使得当N时有：(T(N )-T(N )/T(N ) 0那么，我们就说T(N)是T(N)当N时的渐近性态，或叫T(N)为算法A当N的渐近复杂性而与T(N)相区别，因为在数学上，T(N)是T(N)当N时的渐近表达式。直观上，T(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如当T(N)=3N 2+4Nlog2N +7时，T(N)的一个答

16、案是3N 2，因为这时有：显然3N 2比3N 2 +4Nlog2N +7简单得多。由于当N时T(N)渐近于T(N)，我们有理由用T(N)来替代T(N)作为算法A在N时的复杂性的度量。而且由于于T(N)明显地比T(N)简单，这种替代明显地是对复杂性分析的一种简化。进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T(N)的阶就够了，不必关心包含在T(N)中的常数因子。所以，我们常常又对T(N)的分析进-步简化，即假设算法中用到的所有不

17、同的元运算各执行一次，所需要的时间都是一个单位时间。综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引入五个渐近意义下的记号：、和。以下设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)。则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=(g(N)。这时我们还说f(N)的阶不高于g(N)的阶。举几个例子：(1)因为对所有的N1有3N4N，我们有3N =(N)；(2)因为当N1时有N+10241025N，我

18、们有N +1024=(N)；(3)因为当N10时有2N 2+11N -103N 2，我们有2N 2+11N -10=(N 2)；(4)因为对所有N1有N 2N 3，我们有N2=(N 3)；(5)作为一个反例N 3(N 2)。因为若不然，则存在正的常数C和自然数N0，使得当NN0时有N3C N 2，即NC 。显然当取N =max(N0,C+l)时这个不等式不成立，所以N3(N 2)。按照大的定义，容易证明它有如下运算规则：(f)+(g)=(max(f,g)； (f)+ (g)=(f +g)； (f)·(g)= (f·g)； 如果g(N)= (f(N)，则(f)+ (g)= (

19、f)； (Cf(N)= (f(N)，其中C是一个正的常数； f =(f)； 1.4复杂性渐近阶的重要性计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长

20、和空间需求的增长，对低效算法来说，都是超线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。事实上，我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。我们还是以时间效率为例。设A1,A2,和A6。是求解同一间题的6个不同的算法，它们的渐近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)

21、，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,6。分别解出N2i和N1i的关系，可列成下表：表1-1算法与渐近时间复杂性的关系算法渐进时间复杂性T(N)在C1上可解的规模N1在C2上可解的规模N2N1和N2的关系A1NN11N21N21=10N11A2NlogNN12N22N2210N12A3N2N13N23A4N3N14N24A52NN15N25N25 =N15+log10A6N!N16N26N26 =N16+小的常数从表1-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的

22、增长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长10倍只换取可求解的问题的规模增加log10。当问题的规模充分大时，这个增加的数字是微不足道的。换句话说，对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。从表1-l的最后一列我们还看到，限制求解问题规模的关键因素是算法渐近复杂性的阶，对于表中的前四种算法，其渐近的时间复杂性与规模N的一个确定的幂同阶，相应地，计算机的计算速度的乘法增长带来的是求解问题的规模的乘法增长，只是随着幂次的提高，

23、规模增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶，相应地计算机的计算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。我们在讨

24、论算法复杂性的渐近阶的重要性的同时，有两条要记住：“复杂性的渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N 3<2N，即Nc 时才成立。其中c是方程N 3=2N的解。当N <c时，A5反而比A4有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因一方面是如上所说，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；另方面，在规模小时，决定工作效率的可能不是算法的效率而是算法的简单性，哪一种算法简单，实现起来快，就选用那一种算法。 当要比较的两个算法的渐近复杂性的阶相同时

25、，必须进一步考察渐近复杂性表达式中常数因子才能判别它们谁好谁差。显然常数因子小的优于常数因子大的算法。比如渐近复杂性为N1ogN/l00的算法显然比渐近复杂性为l00NlogN的算法来得有效。2 常见的算法分析设计策略介绍我们一般常见的几种算法分析设计策略主要有：动态规划、贪心算法、回溯法、分支限界法。接下来我主要介绍一下这几种算法。1.1动态规划动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同

26、，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不

27、同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。1.2 贪心算法所谓贪心算法（又称贪婪算法）是指，在对

28、问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路：a.建立数学模型来描述问题。b.把求解的问题分成若干个子问题。c.对每一子问题求解，得到子问题的局部最优解。d.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程： a.从问题的某一初始解出发；b.while 能朝给定总目标前进一步 doc.求出可行解的一个解元素；d.由所有解元素组合成问题的一个可行解。e.下面是一个可以试用贪心算法解

29、的题目，贪心解的确不错，可惜不是最优解。1.3 回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合

30、数较大的问题。回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。用回溯法解题的一般步骤：（1）针对所给

31、问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。1.4 分支限界法分支定界 (branch and bound) 搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。解题步骤：（1）在问题的边带权的解空间树中进行广度优先搜索 （2）找一个叶结点使其对应路径的权最小(最大)（3）当搜索到达一个扩展

32、结点时,一次性扩展它的所有儿子（4）将满足约束条件且最小耗费函数£目标函数限界的儿子,插入活结点表中（5）从活结点表中取下一结点同样扩展（6）直到找到所需的解或活动结点表为空为止3 0-1背包问题的几种算法背包问题是一类具有广泛的实际应用背景的经典NP-hard组合优化问题，在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。因此，

33、借鉴前人的研究成果，开展对解决复杂组合优化问题的算法研究或改进是一项十分优异的工作。Dantzing 在20世纪50年代首先进行了开创性的研究，利用贪心算法求得了0-1背包问题最优解的上届。1974年，horowitz和salmi利用分支限界法解答了背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，Balas和Zemel提出了背包问题的“核”思想，是背包问题的呀牛获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法已经在 0-1背包问题上得到了较好的应用，蚂蚁算法、粒子群等仿生算法也在组合优化问

34、题中得到了很好的应用。综上所述，传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等，由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点。因此此处对精确算法只做简单的描述，对几种近似算法则较为详细的说明了它们的思想和在背包问题中的运用。除了以上几种常见的算法，最近几年又出现了知识进化算法、二进制差异演化算法等新的算法解决背包问题，本文也对它们做一个简介。最后提出了将知识发现的方法引入遗传算法中来解决背包问题，拟提高单存遗传算法的搜索效率和解的质量。3.1 0-1背包问

35、题描述一个旅行者有一个最多能装C公斤重量的背包，已知n个重量和价值分别为ci>0和pi>0(i=1,2,，n)的物品，选择哪些物品装入背包，可使在背包的容量限制之内所装物品的价值最大，这就是背包问题。0-1背包特点是：每种物品都仅有一件，可以选择放入或不放。0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包为1或不装入背包为0。不能将物品i装入背包多次,也不能只装入部分的物品i。021背包问题的主要特点是在选择物品i装入背包

36、时,每种物品仅有一件,可以选择放或不放。3.2动态规划动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。对一个负重能力为m的背包,如果选择装入一个第i种物品,那么原背包问题就转化为负重能力为m2w的子背包问题。由于动态规划算法求解过程中反复出现子问题,且对每次重复出现的子问题都要重新解一次,这需要多花费不少时间,因此动态规划算法的时间复杂度为O ( n* m) ,其中n为物体的个数,m为背包负重。动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。因为背包的最终最大容量未知，所以，我们得从1到M一个一个的试，比

37、如，刚开始任选N件物品中的一个，看对应的M的背包，能不能放进去，如果能放进去，并且还有多少空间，则，多出来的空间能放N-1物品中的最大价值，怎么能保证总选则是最大价值呢，看下表：测试数据：10,33,44,55,6最大容量M物品个数Nj=0-m103C0123456789物品大小W物品价值p编号00000000034i=110004444444451-n 2200045559995633000456691011cij数组保存了1,2,3号物品依次选择后的最大价值。这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这

38、一排背包容量为4,5,6,.10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁?很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9。从以上最大价值的构造过程中可以看出。f(n,m)=maxf(n-1,m), f(

39、n-1,m-wn)+P(n,m)这就是书本上写的动态规划方程.下面是一种实现过程： #include<iostream>using namespace std;int c10100;/*对应每种情况的最大价值*/int knapsack(int m,int n) int i,j,w10,p10; for(i=1;i<n+1;i+) cin>>wi>>pi; for(i=0;i<10;i+) for(j=0;j<100;j+) cij=0;/*初始化数组*/ for(i=1;i<n+1;i+) for(j=1;j<m+1;j+)

40、if(wi<=j) /*如果当前物品的容量小于背包容量*/ if(pi+ci-1j-wi>ci-1j) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更新cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; cout<<"背包中放着重量如下的物品："<<endl; /*确定选取了哪几个物品*/ i=n;j=m; while(i>=0)&&(j>=0) if(pi+ci-1j-wi>ci-1j)&&a

41、mp;(i-1>=0)&&(j-wi>=0) cout<<wi<<" " j=j-wi; i=i-1; else i=i-1; cout<<endl; return(cnm);void main() int m,n; cout<<"输入总背包容量：" cin>>m; cout<<endl; cout<<"输入背包最多可放的物品个数：" cin>>n; cout<<endl; cout<<&

42、quot;输入每一组数据:"<<endl; cout<<"背包所能容纳的最大价值为："<<knapsack(m,n)<<endl;3.3回溯法用回溯法求解0-1背包问题的算法思路是按照物品的单位价值从大到小排序,计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为O ( n3 2n ) , n为物品个数。下面是一种实现过程： #include<io

43、stream> using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m<=n;m+) cout<<bestxm<<" " cout<<endl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 i

44、nt cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int *bestx;/当前最优解 int *x;/当前解 ; int Knap:Bound(int i) /计算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品单位重量价值递减序装入物品 while(i<=n&&wi<=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(i<=n) b+=pi/wi*cleft; return b; void Knap:Backtrack(int i) if(i>n) if(bestp

45、<cp) for(int j=1;j<=n;j+) bestxj=xj; bestp=cp; return; if(cw+wi<=c) /搜索左子树 xi=1; cw+=wi; cp+=pi; Backtrack(i+1); cw-=wi; cp-=pi; if(Bound(i+1)>bestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator<=(Object a)const return (d&

46、gt;=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i<=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W<=c) return P;/装入所有物品 /依物品单位重量排序 float f; for( i=0;i<n;i+) for(int j=i;j<n;j+)

47、 if(Qi.d<Qj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i<=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; dele

48、te K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; cout<<"请输入背包个数："<<endl; cin>>n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout<<"请输入个背包的价值："<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<"请输入个背包的重量："<

49、<endl; for(i=1;i<=n;i+) cin>>wi; cout<<"请输入背包容量："<<endl; cin>>c; cout<<Knapsack(p,w,c,n)<<endl; 3.4 贪心算法在求解0-1背包问题时,对贪心算法可以使用一些策略, 使其得到的解更接近最优解。具体方案如下:(1) 价值优先策略:从剩余的物品中,选取价值最大的可以装入背包的物品。此时,价值最大的优先被装入背包,然后装入下一个价值最大的物品,直到不能再装入剩下的物品为止。(2) 重量优先策略:从剩余的

50、物品中选取重量最小的物品装入背包中,这种策略一般不能得到最优解。(3) 单位价值优先策略:根据价值/重量的比值,按照每一次选取剩下的物品中比值最大的物品装入背包,直到不能再装入为止。以上三种策略都不能保证得到最优解,但三种策略相比较而言,第三种策略与最优解相差较小。如果可以选择物品的一部分,用单位价值策略可以保证得到最优解。在贪心算法时间复杂度的估算中,由于需要对重量或价值或两者的比值进行排序，所以贪心算法的时间复杂度为O(n*logn)。下面是一种实现过程： #include <iostream.h>#include <math.h>#include <stri

51、ng.h>#include "time.h"#include "windows.h"#include <stdlib.h>#include <stdio.h>#define num 100void bagloading(int x,float p,float w,float c,int n) /x取值为0或1，xi=1当且仅当背包i背装载； /p是物品价值； /w是物品重量； /c表示背包的容量； /n表示物品的件数； float t,k,pwnum; int i,j,m,kk; for(i=0;i<n;i+) pwi=pi/wi; /对各个点的坐标按由大到小进行排序(使用改进的冒泡排序) m=n-1; while (m>0) kk=0; for(j=0;j<m;j+) if (pwj<pwj+1) t=pj; pj=pj+1; pj+1=t; k=wj; wj=wj+1; wj+1=k; kk=j; m=kk; /按p/w次序从大到小选择物品 i=0; while(i<n