01背包问题求解方法综述.doc

实用文档算法分析与设计大作业实验题目：0-1背包问题求解方法综述 组 员：班 级：指导老师：文案大全0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的 NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了 0-1背包问题的数学模型，刻划了最优解的结构特征,建立了求最优值的递归关系式最后对四种算法从不同角度进行了对比和总结关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法0.引言0-1背包问题是指给定n个物品，每个物品均有自己的价值Vi和重量 wi(i=1,2,…,n),再给定一个背包,其容量为W要求从n个物品中选出一部分物 品装入背包，这部分物品的重量之和不超过背包的容量，且价值之和最大单个物 品要么装入，要么不装入很多问题都可以抽象成该问题模型，如配载问题、物资 调运［1］问题等，因此研究该问题具有较高的实际应用价值目前，解决0-1背包 问题的方法有很多，主要有动态规划法、回溯法、分支限界法、遗传算法、粒子 群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。

其中动态规划、回溯法、分支限界法时间复杂性比较高 ，计算智能算法可能出现局部收敛,不一定能找出问题的最优解文中在动态规划法的基础上进行了改进， 提出一种求解0-1背包问题的算法，该算法每一次执行总能得到问题的最优解， 是确定性算法，算法的时间复杂性最坏可能为0(2n)1.0-1背包问题描述0-1背包问题(KP01)是一个著名的组合优化问题它应用在许多实际领域 ,如项目选择、资源分布、投资决策等背包问题得名于如何选择最合适的物品放 置于给定背包中本文主要研究背包问题中最基础的 0/1背包问题的一些解决方 法为解决背包问题，大量学者在过去的几十年中提出了很多解决方法解决背 包问题的算法有最优算法和启发式算法［2］,最优算法包括穷举法、动态规划法、 分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子 算法等一些智能算法0-1背包问题一般描述为：给定n种物品和一个背包物品i的重量是w(i), 其价值为v(i)，背包的容量为c问应该如何选择装入背包的物品， 使得装入背 包中的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装 入背包不能将物品i装入背包多次，也不能只装入部分的物品i。

因此，该问 题称为0-1背包问题此问题的形式化描述是，给定c 0, wi . 0，vi . 0, < i < n，要求找出一个nnn元0-1向量(X，X2,…，Xn)，Xi €{0冷，口兰n，使得》wxi兰c，而且瓦vixii =1 i J达到最大n数学模型：max v v Xii =1n约束条件：' WN ， X {0,1},仁匕nid2.0-1背包问题的求解算法2.1 蛮力算法(brute force method )2.1.1基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成，可 用子集数表示在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否 可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍 历过的最大价值2.1.2代码实现：#in clude#i ncludeusing n amespace std;#defi ne N 100 // 最多可能物体数struct goods // 物品结构体{int sig n; // 物品序号int w; // 物品重量int p; // 物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(i nt a,i nt b){retur n a n-1){if(bestP

贪心选择即它总是做出当前 最好的选择[4]贪心选择性质指所求问题的整体最优解可以通过一系列局部最 优选择，这是贪心算法与动态规划算法的主要区别贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件 在枚举剩下数据与当前已经选取的数据组合获得的解中， 提取其中能获得最优解的唯一的一个数据，加入结果数据中，直到剩下的数据不能再加入为止 ⑹贪心算法不能保证得到的最后解是最佳的，也不能用来求最大或最小解问题，只能 求满足某些约束条件的可行解范围2.2.1算法设计用贪心算法解决0-1背包问题一般有以下三种策略：价值最大者优先：在剩余物品中，选出可以装入背包的价值最大的物品， 若背包有足够的容量，以此策略，然后是下一个价值最大的物品 但这种策略背包的承重量不能够得到有效利用，即得不到最优解例如：n=3,w=[50,20,20],v=[10,7,7]c=55, 得到的解是 x=[1,0,0],这种方案的总价值为10,而最优解为[0,1,1],总价值为14重量最小者优先：在剩余物品中，选择可以装入背包的重量最小的物品但这种策略，不能保证重量小的是最有价值的，也不能得到最优解例如： n=2,w=[10,20],v=[5,100],c=25 ，得到的解为 x=[1,0],而最优解是[0,1]。

单位价值最大者优先：根据价值与重量的比值 《/w，即单位价值，在剩下的物品中依次选取比值最大的物品装入背包 这种策略也不能得到最优解例如：n=3,w=[20,15,15],v=[40,25,25], v / wi =[2,5/3,5/3],c=30, 得到的解 x=[1,0,0],而最优解是[0,1,1]但它是直觉上的一个近似解本文讨论该策略策略3的具体步骤为：第一步：计算每个物品的价值比ri =vi / wi，i=1,2，…,n第二步：对物品的价值比非递增排序第三步：重复下面操作，直到有序列表中留下物品如果列表中的当前物品 能够装入背包，就将它放入背包中，否则，处理下一个物品2.2.2 编程实现#i nclude"stdafx.h"#i nclude #in clude#i ncludevWi ndows.h>using n amespacestd;#defi ne max 100 //void package© nt v[],i nt w[],i nt n ,i nt c) //{doublea[max];in ti,totalv=0,totalw=0,i ndex[max]; for(i=0;i