《0-1背包问题求解方法综述》由会员分享，可在线阅读，更多相关《0-1背包问题求解方法综述（34页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计大作业实验题目：0-1背包问题求解措施综述组 员: 班级：指引教师：0-1背包问题求解措施综述【摘要】:01背包问题是一种典型的N-hrd组合优化问题,现实生活中的诸多问题都可以以它为模型。本文一方面对背包问题做了论述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解,分析了01背包问题的数学模型，刻划了最优解的构造特性，建立了求最优值的递归关系式。最后对四种算法从不同角度进行了对比和总结。【核心词】：01背包问题；蛮力解法；动态规划算法；贪心算法;回溯解法。0.引言0-1背包问题是指给定n个物品,每个物品均有自己的价值v和重量wi(i1，2,n）,再给定一种背
2、包，其容量为W。规定从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。单个物品要么装入,要么不装入。诸多问题都可以抽象成该问题模型,如配载问题、物资调运1问题等，因此研究该问题具有较高的实际应用价值。目前，解决01背包问题的措施有诸多,重要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。其中动态规划、回溯法、分支限界法时间复杂性比较高，计算智能算法也许浮现局部收敛,不一定能找出问题的最优解。文中在动态规划法的基本上进行了改善,提出一种求解0-1背包问题的算法，该算法每一次执行总能得到
3、问题的最优解，是拟定性算法,算法的时间复杂性最坏也许为O（2n)。1.0-1背包问题描述0-1背包问题(KP）是一种出名的组合优化问题。它应用在许多实际领域,如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适的物品放置于给定背包中。本文重要研究背包问题中最基本的01背包问题的某些解决措施。为解决背包问题，大量学者在过去的几十年中提出了诸多解决措施。解决背包问题的算法有最优算法和启发式算法2，最优算法涉及穷举法、动态规划法、分支定界法、图论法等,启发式算法涉及贪心算法、遗传算法、蚁群算法、粒子算法等某些智能算法。-1背包问题一般描述为：给定种物品和一种背包。物品i的重量是w（i)，其
4、价值为v(i）,背包的容量为。问应当如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入背包的物品时，对每种物品只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此,该问题称为-背包问题。此问题的形式化描述是,给定,规定找出一种n元0-1向量,使得，并且达到最大。数学模型：约束条件：， 2.背包问题的求解算法2.1蛮力算法（bruteforce meod）2.11基本思想:对于有n种可选物品的0/1背包问题，其解空间由长度为n的-1向量构成,可用子集数表达。在搜索解空间树时,深度优先遍历,搜索每一种结点,无论与否也许产生最优解，都遍历至
5、叶子结点，记录每次得到的装入总价值,然后记录遍历过的最大价值。.1.2代码实现:#ncuencldeusng nmepace st;defin N 100 /最多也许物体数ruct gods /物品构造体 int sign; /物品序号 i ； /物品重量 itp；/物品价值N;bo m(goods a,goods ) reurn （a.p.w)(b.p/b.);it max(na,t b) rernab?:；i n,C,bet=,cp=0，=0;in N,cx;/*蛮力法求解01背包问题nt orce(int i) if(in-) f(bestPc&cw+aiw=C) for (nt k=0
6、;kn;k+) Xkxk;/存储最优途径 besP=cp; return estP; ccw+ai.w; ccp+ai.; ci1; /装入背包 Force（i); c=cw-ai.； c=cp-aip; xi=0； /不装入背包 Forc(1); eturnbestP;int KnpSck1(in n，godsa，n ，tx) Force(0); return bestP;in an(） g b; pint（物品种数n: ); scanf(d,n）; /输入物品种数 rnf(背包容量C: ); anf（%,); /输入背包容量 r (inti=0;in;i+) /输入物品i的重量w及其价值
7、prntf(物品d的重量%及其价值v%:,i+1，i1，+1）; caf(%d,&ai.w,ai.); i=ai; int u=Knap1(n,C,X);/调用蛮力法求0/1背包问题 printf(蛮力法求解0/1背包问题:nX= ); fr(i=0；in;i+) coi ；/输出所求Xn矩阵 rntf( 装入总价值dn,sm1)； betP=0,cp=0,cw=0;/恢复初始化2.3复杂度分析：蛮力法求解0/1背包问题的时间复杂度为:22贪心算法（eeagith） 贪心算法通过一系列的选择来得到问题的解。贪心选择即它总是做出目前最佳的选择4。贪心选择性质指所求问题的整体最优解可以通过一系列局
8、部最优选择,这是贪心算法与动态规划算法的重要区别。 贪心算法每次只考虑一步，每一步数据的选用都必须满足局部最优条件。在枚举剩余数据与目前已经选用的数据组合获得的解中，提取其中能获得最优解的唯一的一种数据，加入成果数据中,直到剩余的数据不能再加入为止6。贪心算法不能保证得到的最后解是最佳的，也不能用来求最大或最小解问题，只能求满足某些约束条件的可行解范畴。2.2算法设计用贪心算法解决0-1背包问题一般有如下三种方略:价值最大者优先：在剩余物品中,选出可以装入背包的价值最大的物品，若背包有足够的容量,以此方略,然后是下一种价值最大的物品。但这种方略背包的承重量不可以得到有效运用，即得不到最优解。例
9、如：=3,w=50,20，20,=0，,c=5,得到的解是=1,0,0,这种方案的总价值为1，而最优解为0,1,总价值为14。重量最小者优先:在剩余物品中，选择可以装入背包的重量最小的物品。但这种方略，不能保证重量小的是最有价值的，也不能得到最优解。例如:n2,w,20，v5，00,c5,得到的解为x=,0,而最优解是0,。单位价值最大者优先：根据价值与重量的比值/,即单位价值,在剩余的物品中依次选用比值最大的物品装入背包。这种方略也不能得到最优解。例如：n=3,=20,15，4,25,5，/=2,/3,5/,c=30,得到的解=1,0,0,而最优解是0,1。但它是直觉上的一种近似解。本文讨论
10、该方略。方略的具体环节为:第一步：计算每个物品的价值比=/，i=1,2,，n。第二步:对物品的价值比非递增排序。第三步:反复下面操作，直到有序列表中留下物品。如果列表中的目前物品可以装入背包,就将它放入背包中，否则，解决下一种物品。2.22编程实现#cludetdx.h#incude #include #incdeigamesacest;#define mx 10 自定义物品最大数voi packge（nt v,int w，it n,int ) /定义包函数 dubleax; in,toav=,totaw0,idmx; for(i=;in；i+) ai=(due）v/wi; /单位价值计算 exii; fo(i=;in；i+) for(int j=0；n-i;j+) if(aa+1) /进行循环判断 obe b=j; aj=aj1; a+1=b; int =v; v=v+1; v1c; ntdj; wj+1; wj+1=d; in id； inexj=indexj+1； iexj+1e; cu单位价值:; /输出单位价值 fr(=0；i;i+) cotai ; tel物品价值：; /输出物品价值 fo
