背包问题求解方法综述.docx
24页
算法分析与设计大作业实验题目：0-1背包问题求解方法综述组 员：班 级：指导老师：0-1背包问题求解方法综述【摘要】0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型本文首先对背包问题做了阐述，然后用蛮力解法、 动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了 0-1背包问 题的数学模型，刻划了最优解的结构特征,建立了求最优值的递归关系式最后 对四种算法从不同角度进行了对比和总结关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法0.引言0-1背包问题是指给定n个物品，每个物品均有自己的价值vi和重量wi(i=l,2,…,n),再给定 一个背包，其容量为W要求从n个物品中选出一部分物品装入背包，这部分物品的重量之和 不超过背包的容量，且价值之和最大单个物品要么装入，要么不装入很多问题都可以抽象 成该问题模型，如配载问题、物资调运［1］问题等,因此研究该问题具有较高的实际应用价 值目前，解决0-1背包问题的方法有很多，主要有动态规划法、回溯法、分支限界法、遗传 算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法 等。
其中动态规划、回溯法、分支限界法时间复杂性比较高，计算智能算法可能出现局部收 敛,不一定能找出问题的最优解文中在动态规划法的基础上进行了改进，提出一种求解0-1 背包问题的算法,该算法每一次执行总能得到问题的最优解，是确定性算法,算法的时间复杂 性最坏可能为O(2n)1.0T背包问题描述0-1背包问题(KP01)是一个着名的组合优化问题它应用在许多实际领域,如项目选择、 资源分布、投资决策等背包问题得名于如何选择最合适的物品放置于给定背包中本文主 要研究背包问题中最基础的0/1背包问题的一些解决方法为解决背包问题，大量学者在过去的几十年中提出了很多解决方法解决背包问题的算 法有最优算法和启发式算法［2］，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法0-1背包问题一般描述为：给定n种物品和一个背包物品i的重量是w(i),其价值为 v(i)，背包的容量为c问应该如何选择装入背包的物品，使得装入背包中的物品的总价值 最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包不 能将物品i装入背包多次，也不能只装入部分的物品i。
因此，该问题称为0-1背包问题此问题的形式化描述是，给定c > 0, w > 0, v > 0,1 < i < n，要求找出一个n元0-1向量i i，x)，x e {0,1},1 < i < n，使得n i工wx < ci i而且£ vx达到最大i ii=1数学模型：max £ v xi ii = 1约束条件：Lwx < c x G{0,1}1 贪心选择即它总是做出当前最好的选择 [4]贪心选择性质指所求问题的整体最优解可以通过一系列局部最优选择，这是贪心算法 与动态规划算法的主要区别贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件在枚举剩下 数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加 入结果数据中，直到剩下的数据不能再加入为止[6]贪心算法不能保证得到的最后解是最 佳的，也不能用来求最大或最小解问题，只能求满足某些约束条件的可行解范围用贪心算法解决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]。 单位价值最大者优先：根据价值与重量的比值v/w，即单位价值，在剩下的物品中i i依次选取比值最大的物品装入背包这种策略也不能得到最优解例如： n=3,w=[20,15,15],v=[40,25,25], v /w =[2,5/3,5/3],c=30,得到的解 x=[1,0,0],而最优解i i是[0,1,1]但它是直觉上的一个近似解本文讨论该策略策略3的具体步骤为：第一步：计算每个物品的价值比r = v / w， i=1,2,…,nIII第二步：对物品的价值比非递增排序第三步：重复下面操作，直到有序列表中留下物品如果列表中的当前物品能够装入背包，就将它放入背包中，否则，处理下一个物品2.2.2编程实现#include"s tdafx.h"#include
