0/1背包问题
研究与开发
0-1背包问题算法分析与研究
周
斌1
,张
莹2
,黄志军1
(1.中南民族大学,武汉430074;2.华中科学技术大学,武汉430074)
提出背包问题在现实生活中具有广泛的
ÁÁ摘要:0/1背包问题是计算机算法中一个经典问题。
应用,从理论入手,给出背包问题的数学描述,并对0-1背包问题的四种经典算法:分支界限法、动态规划法、近似算法、遗传算法的算法思想进行详细描述,并对四种算法在实现的时间,空间和准确性等性能方面进行分析和对比,总结四种方法实现的优缺点,并得出结论:在不同的约束条件下,四种算法各有优劣,但遗传算法应该是未来发展的方向。
关键词:0-1背包;分支-界限;动态规划;近似算法;遗传算法
1问题的提出
背包问题在我们的现实生活中具有广泛应用,
0-1背包问题(0-1KnapsackProblem)是一类最简单的背包问题,属于组合优化问题,即在不超过背包容量的条件下获得最大的价值。
如能提出求解此类问题高效的算法,则具有很好的经济价值和决策价值,例如物流公司的货物发配问题,集装箱的运载问题等,如何才能获得最大利润。
我们对此问题的进行一般描述如下:
一个登山者想要选择不同的物品装满他的背包。每个物品有其重量和价值。背包的最大承重为M,现有n个物品可供选择装入背包,第i个物品重量为
2算法思想描述及其性能分析
在对背包问题的研究中,人们已提出了许多解
2.1常用算法
法,例如[1,2]:分支界限法(BranchandBound)[4]、动态规划法(DynamicProgramming)[3,7]、近似(ApproximateSolu-
wi,价值为pi,假定物品i的一部分xi(0≤xi≤1)放入背包,获得价值为xipi,由于背包最大承重为M,要求装入物品总质量不过超过M,问登山者旅行者应该如何选择物品装入背包,在不超过背包装载总重量的条件下使得装入物品的价值总和达到最大值?
背包问题的数学描述如下:要求找到一个n元向量(x1,x2,…,xn),在满足约束条件:满足约束条件
tions)[5]、遗传算法(GeneticAlgorithm)[6]等等。
(1)分支界限法(BranchandBound)
第一个基于分支界限法的背包问题求解是由
HorowitzandSahni,NaussandMartelloandToth于20世纪70年代提出。
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支。这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
分枝界限法是组合优化问题的有效求解方法,对
Σxw≤M且0≤x≤1的情况下,使得目标函数max
ii
i
Σxp,,其中,1≤i≤n;M>0;w>0;p>0。满足约束条件
ii
i
i
的任何向量都是一个可行解,而使得目标函数达到最大的那个可行解则为最优解。
如果对背包问题进行扩展,在装入物品时只允许全装或者不装,不允许装入物品的部分,也就是xi=
现
代计算机(总第三
○
1或者xi=0。此时成为0-1背包问题。
收稿日期:2009-04-02
修稿日期:2009-05-30
作者简介:周斌,讲师,研究方向为软件理论、虚拟化计算
ODERNCTER2009.6
趶趦
九
期)
兰O1一 背包 问题 算法分 析 与研 究周 斌 ,张 莹 ,黄志军 (.南 民族大学 ,汉407 1中武304;2华 中科 学技术大学,汉407 .武304) // 摘 要:0/ ...
0-1背包问题算法分析与研究_自然科学_专业资料。0-1背包问题算法分析与研究竺兰竺O一1背包问题算法分析与研究周 斌1 ,张莹2 ,,/ ,黄志军1 (1.中南民族...
1 背包问题的算法研究李北斗 (中国地质大学信息工程学院 武汉 430074) 摘 0 /...下面对动态规划的算法进行一下相应的算法 分析 , 首先是时间复杂度 , 从上面...
+86-551-5690963 5690964 0-1 背包问题之穷举、搜索、动态规划算法探讨曹周进(...算法分析:为了得到能放进背包物品的最大总价值。 我们可以在 n 种物 品中,...
并在 背包算法的时间复杂 , 度和空间复 杂度 两发面进行 简要 分析 关键 词...研究 表 明该 算 法具有 许 多优 良的性 质〔〕针对 0 优化设 计问题 ...
实践与经验 0/1 背包问题动态规划算法的探讨孙建中( 中国地质大学 (武汉 ) 信息工程学院, 武汉 430074)要: 0/1 背包问题是运筹学中的著名问题, 有重要的使用...
eduf@cccc.net.cn 0/1 背包问题及其解法研究黄波,蔡之华 (中国地质大学计算机...方法的基本原理,提出了求解 0/1 背包问题的算法思想,并对算法进行分析, 提出...
0-1背包问题 6页 免费 算法设计与分析实验报告... 6页 免费...研究多阶段 决策过程的优化问题时提出的,把多阶段决策过程转化为一系 列单阶段...
0-1背包问题研究及算法策略比较分析_理学_高等教育_教育专区。0-1背包问题研究及算法策略比较分析成绩 数学与物理科学学院《算法分析与设计》课程考查论文 题专班...
背包问题的算法设计与分析研究 答案是否定的, 还以上面的实例说明, 采用贪婪法求的解向量为( 1,0,0), 最大价值为 60, 很明显 ,(0,0,1)优于前者,最大...
热门文档