文档背包问题

背包问题报告小组成员：张灿、吴雪涛、高坤、占强、习慧平小组分工情况小组成员查找资料制作ppt编写程序讲解ppt制作报告张灿ⅴⅴⅴⅴⅴ吴雪涛ⅴ高坤ⅴⅴ占强ⅴ习慧平ⅴ背包问题背包问题的历史由来它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。背包问题的描述背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？背包问题的定义我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：maximizesubjectto路径较短，则该蚂蚁从巢穴到食物源后再返回巢穴的时间也就较短，这样同时间内在较短路径上蚂蚁分泌的信息素就会较多。后面的蚂蚁将根据其他蚂蚁留下来信息素的多少而选择路径，某一条路径上的信息素越多，则这条路径被选择的概率越大。蚂蚁群体的这种集体行为构成了一种学习信息的正反馈机制，蚂蚁之间通过信息素来交流信息。蚁群算法模拟了这种优化机制，通过个体之间的信息交流与协作来寻找最优解。蚁群算法现已成功运用在TSP、图像处理、车辆路径系统、通信系统等领域。它具有较强的鲁棒性、分布性、全局优化性和易与其它优化算法融合的优点,现已是解决NP-hard问题的一个有效工具。蚁群算法解决0/1背包问题的核心是：在某一物品上聚集的信息素越多，则该物品被选择的概率就越大。背包问题的蚁群算法求解过程是：①设置迭代次数；②将各蚂蚁置于相应变量的0、1位置点；按转移概率移动各蚂蚁；按强度更新方程更新信息素轨迹；记录当前最佳蚂蚁位置；③返回步骤②循环直到满足退出条件。就蚁群算法而言当处理的数据比较小时其具有很快的收敛速度，而随着数据规模的增大算法的收敛速度明显降低。蚁群算法在减少寻优计算量和缩短算法运行时间方面，有待进一步改进。针对蚁群算法的缺点，许多学者对蚁群算法进行了改进。赵朝卿，胡小兵等提出了一种求解0-1背包问题的混合型算法(KPAICACA)，先利用蚁群算法求优化解，然后利用抗体克隆选择算法扩大解的搜索空间，使得在收敛速度和寻优能力两方面都有明显改善。具体方法是：每个物品i的属性有重量ci，价值pi和信息素τi，即信息素积累在物品上。选择物品i的期望度为ηi=pi/ci。每只蚂蚁都附一个背包和一个禁忌表，蚂蚁将根据选中物品的重量来决定是否将其装入背包。若物品装入背包而不超过其容量，则继续选择下一个物品；否则将其编号放入禁忌表中，以后选择物品时不再考虑。经过n次选择，构建了一个由物品编号表示的解，当m只蚂蚁都构建了自己的解，将这些编号解变换为0-1序列解，每个序列解被视做一个抗体，抗体编码的长度为n，抗体群的规模等于蚂蚁种群的规模m。随后对抗体群进行克隆、变异和选择操作。抗体免疫克隆算法搜索完成后，根据背包中物品的价值总和P，记录最优解以及对应的物品价值总和，并对物品上的信息素进行更新。5.2.3遗传算法遗传算法己被广泛地应用组合优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体),并将每一个染色体编码成串的形式,再根据预定的目标函数对每个个体进行评价,给出一个适应值。算法将根据适应度值进行它的寻优过程,遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力。遗传算法的时间复杂度为O(T*n^2),其中T为迭代次数，n为种群个数。运用简单的遗传算法（SGA，SimpleGeneticAlgorithm）求解背包问题时若问题规模不大也能够得到最优解或近似最优解，但当规模较大时，算法容易早熟，得不到比较理想的结果，所以需要对其进行改进。遗传算法解决背包问题处理约束条件的方法有两种一种方法是用罚函数法改造目标函数；另一种方法是结合贪心算法改造染色体的解码过程。其中将遗传算法与贪心算法结合，实际上是一种混合遗传算法。几种常用算法的比较从表中看出，以上各种算法都有其自身的不足，大体分为两类问题：一是不能在有限时间内求出解，二是陷入局部最优。0/1背包问题的展望由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点，出现了很多的新的算法。下面介绍几种。DNA计算，是基于生化反应的一种全新的计算模式。石晓龙等就一个NP完全问题（0-1背包问题）设计了一种基于DNA链长度映射背包物品重量权值的一类带权值型组合优化问题的DNA分子计算方法。该算法目的是用DNA分子计算模式解决带有数值运算特征的组合优化问题。DNA计算的时间复杂度为o(n^2)。知识进化算法是在分析知识进化机制基础上提出的一种可以解决复杂问题的新型优化方法，能广泛用于解决函数优化和组合优化问题。马慧民等根据0-1背包问题的特点，提出用于求该问题的知识进化算法方案，实现了算法并取得了良好的结果。差异演化算法(DE)是一种基于群体差异的演化算法，是RainerStorn和KennethPrince在1995年提出的，属于直接搜索算法。该算法具有收敛速度快、操作简单，易编程实现，极强的稳健性等优点。传统差异演化算法的研究及应用主要集中在连续搜索空间的问题上，对于0-1背包问题无法对其进行求解。蔡鸿英等通过采用新的变异方法，提出一种新的采用二进制编码技术处理的差异演化算法，阐明了该算法求解背包问题的具体实现过程。通过多个0-1背包问题进行仿真，结果证明该算法在解0-1背包问题时能达到最优解且收敛速度较快。但是差异演化算法的收敛性、理论依据等还不完善，有待进一步研究。八：附录动态规划求解01背包问题源程序及运行结果：#include<iostream>#include<fstream>#defineN100usingnamespacestd;intn,weight,p[N],w[N];voidReadData(){ifstreamifs("a.txt",ios::in); ifs>>n>>weight; for(inti=1;i<=n;i++) {ifs>>w[i]>>p[i];}}intcishu=0;voidPackage(){ intsp,sw,cw=weight; intm[N][N]; for(inti=0;i<=weight;i++) if(i>=w[n])m[n][i]=p[n]; else m[n][i]=0; for(i=n-1;i>=1;i--) {for(intj=0;j<=weight;j++){ if(j>=w[i]&&m[i+1][j]<m[i+1][j-w[i]]+p[i]) {m[i][j]=m[i+1][j-w[i]]+p[i];cishu++;} else m[i][j]=m[i+1][j];} }cout<<"背包所装物品:"<<endl; cout<<"i"<<"w(i)"<<"p(i)"<<endl; for(sw=0,sp=0,i=1;i<=n-1;i++) { if(m[i][cw]>m[i+1][cw]) { cw-=w[i];sw+=w[i];sp+=p[i]; cout<<i<<""<<w[i]<<""<<p[i]<<""<<endl; } } if(m[1][weight]-sp==p[n]) { sw+=w[n];sp+=p[n]; cout<<i<<""<<w[i]<<""<<p[i]<<""<<endl; } cout<<"w="<<sw<<"pman="<<sp<<endl;}voidmain(){ReadData();Package();cout<<"模拟时间复杂度为："<<cishu<<endl;}程序给出的测试用数据：运行结果如下：回溯法求解01背包问题源程序及运行结果：#include<iostream>#include<string>usingnamespacestd;intpath_num=1;constintn=6;//物品数量doublec;//容量doublebestprice;doublecurrentprice;doublebestweight;doublecurrentweight;boolbestchoice[n];//选择boolcurrentchoice[n];structnode{ doubleweight; doublevalue;}data[6];voidinit()//初始化{ c=60; data[0].weight=15; data[1].weight=17; data[2].weight=20; data[3].weight=12; data[4].weight=9; data[5].weight=14; data[0].value=32; data[1].value=37; data[2].value=46; data[3].value=26; data[4].value=21; data[5].value=30; bestprice=0; currentprice=0; currentweight=0; memset(currentchoice,false,sizeof(currentchoice)); cout<<endl;}intcishu=0;voidtrack(intk)//k=012层回溯搜索{ if(k>=n) { if(currentprice>bestprice) { bestprice=currentprice; bestweight=currentweight; cishu++; for(inti=0;i<n;i++) {bestchoice[i]=currentchoice[i]; cishu++; } } return; } if(currentweight+data[k].weight<=c)//选择 { currentweight+=data[k].weight; currentprice+=data[k].value; currentchoice[k]=true; track(k+1); currentweight-=data[k].weight; currentprice-=data[k].value; currentchoice[k]=false; cishu++; } { track(k+1);}}voidshow_result()//显示结果{ cout<<"求出背包最大价值:"<<bestprice<<endl; cout<<"此时背包的重量:"<<bestweigh