0-1背包问题算法分析与研究

线性规划的运用

兰 O1一背包问题算法分析与研究周斌，张莹，黄志军(.南民族大学，汉 4 07 1中武 3 0 4;2华中科学技术大学，汉 4 0 7 .武 3 0 4)

//

摘

要：0/ 1背包问题是计算机算法中一个经典问题。提出背包问题在现实生活中具有广泛的应用，理论入手，出背包问题的数学描述，对 0从给并 -1背包问题的四种经典算法：支分

界限法、态规划法、动近似算法、遗传算法的算法思想进行详细描述。并对四种算法在实现的时间，间和准确性等性能方面进行分析和对比。结四种方法实现的优缺点，得出结空总并

论：不同的约束条件下 .在四种算法各有优劣.但遗传算法应该是未来发展的方向。 关键词：0—1背包；分支一限；动态规划；近似算法；遗传算法界

1问题的提出 背包问题在我们的现实生活中具有广泛应用 . 如能提出求解此类问题高效的算法 .具有很好的经则济价值和决策价值.如物流公司的货物发配问题。例 集装箱的运载问题等。何才能获得最大利润。如 我们对此问题的进行一般描述如下：一

0 l背包问题 f— n pa kPo lm是一类最一 0 1K a sc rbe )简单的背包问题 .于组合优化问题 .在不超过背属即包容量的条件下获得最大的价值

2算法思想描述及其性能分析 21常用算法 .在对背包问题的研究中.人们已提出了许多解法。如：支界限法 B a c n o n )动态规例分 rn ha dB u d￣、

个登山者想要选择不同的物品装满他的背包

每个物品有其重量和价值 背包的最大承重为 M.现有 n个物品可供选择装入背包 .第 i物品重量为个W.,

划￣: y a cPormmig3、 ( n mi rga n )￣近似( p rxma ou D E ' A poi t S l— e t n)、 i ss遗传算法( eei A grh )等等。 o[ l G n t lo tm t c i￣( )支界限法 (rn ha dB u d 1分 B a c n o n 1第一个基于分支界限法的背包问题求解是由Hoo t n a n . u s n rel n o

h于 rwi a d S h i Na s a d Ma tl a d T t z o

价值为 P,定物品 i的一部分 X 0 i 1放入 .假，≤x≤ ) (

背包，得价值为 x;由于背包最大承重为 M,求 获 i, P要装入物品总质量不过超过 M.登山者旅行者应该如问何选择物品装入背包 .不超过背包装载总重量的条在

2 0世纪 7 0年代提出分支定界法的基本思想是对有约束条件的最优化问题的所有可行解 (目有限 )间进行搜索。算数空该法在具体执行时 .全部可行的解空问不断分割为越把来越小的子集 (为分支 )并为每个子集内的解的值称，计算一个下界或上界 (为定界 )在每次分支后。称。对

件下使得装入物品的价值总和达到最大值？背包问题的数学描述如下：要求找到一个 n元

向量 x'2…,n在满足约束条件：足约束条件 x, x, )满

∑≤ 且0 1情况使标函 a≤≤的下，得目数mxx 其中，≤i; 0 w> p 0满足约束条件 i p 1≤n M>;,。。 0;>

凡是界限超出已知可行解值那些子集不再做进一步现 分支。这样，解的许多子集 (即搜索树上的许多结点 )代

的任何向量都是一个可行解 .而使得目标函数达到最大的那个可行解则为最优解一

就可以不予考虑了，从而缩小了搜索范围。这一过程计何子集的界限。因此这种算法一般可以求得最优解。

直进行到找出可行解为止 .该可行解的值不大于任算^

如果对背包问题进行扩展 .装入物品时只允在

机

许全装或者不装，不允许装入物品的部分，就是 x 也 i:1者 x0或 -。此时成为 0 1包问题。 _—背

分枝界限法是组合优化问题的有效求解方法 . 总对

第

三收稿日期：0 9 0—0修稿 1:0 9 5 3 2 0— 4 2 3期 2 0—0— 0

O

作者简介：斌，师，究方向为软件理论、拟化计算周讲研虚

九 期

MDR OPTR唧.囝 OENC E 6 MU 2

线性规划的运用

\于 o l背包问题 .步骤如下所述： _其

:= p( 1 m) -, i

①计算每个节点即解集中部分物品的重量

和。如当前重量超过了背包容量 w.则将在该节点下的所有子树删除：

_) l+ 'p l}一

初条是：1 )0 始件 P,:, m (m{埘动态规划算法时间复杂度阁：上面算法的执行从过程中可以看出假设有 Q( )子问题，一个子问 n个每

②计算上一级分支的所有可能解的价值，如果当前分支的价值比较小或相等则删除分支界限法并不用于纯粹的深度优先模式 .是而

最好优先：选择最有希望达到目标结点的结点优先扩展。此算法由于从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较 .出找 限界最小的结点，结点即为下次分支的结点。这种此

题最多需要 m次决策.则计算的频率为 m .回溯的频率为 n,么整个过程的算法的时间复杂度为 T n那 ()

= m+即为 Q(m)然后， n n。 n。我们再看一下另一个考察指标空间复杂度.根据上面的得到的计算频率和回溯频率，根据空间复杂度计算的原则可知为 Q( ) n。从上面的分析可以看出动态规划法的时间复杂度和空间复杂度均成直线增长。在整个计算过程中，择一种选行之有效的决策方法是至关重要的 .够分解成比较能

决策的优点是检查子问题较少 .能较快地求得最佳解。

但在最坏情况下 .可避免地要在整个状态空间不

树上进行搜索 .要存储很多叶子结点的限界和对应的耗费矩阵。需指数级的时间复杂度 021此时其空间 (n,消耗也较大

容易解决的子问题，是决策设计的最佳标准。 第一个近似算法是基于动态规划法定义的其思想是：如果价值用其他方法衡量 .可能减少运行时间 . 但它是以解的准确性为代价的。具体做法： P 2代用 _/替 P( 1…,)实际上是将 P的最后 k位删除， i=, n。 i i如

可以说一个分支定界求解方法的效率基本上由 值界方法决定 .若界估计不好 .极端情况下将与穷在举搜索没多大区别。 () 2动态规划法(y a cPorm n ) D nmi rga mig 动态规划法在背包问题的应用是由 Gl r i e和 mo Gm n o o y提出 动态规划的基本思想：一个比较大的问题

逐层将

果我们期望相对误差最大值为 e 0整数 k即为满足>.以下条件的最大整数： (k1 p a)= ( 2- ) m x< e或者 k>lg n/ _ o￣ - (+ .m xn,中 p x为估计得到的最大价值。 1 e a/)其 p ma 而对于一个好的近似优化算法其优化效果常常和其他优化算法的效果一样好 .它的时间消耗却少但得多。这就是关于背包问题存在好几种近似算法的原因上面所述的第一个近似算法是基于动态规划法定义的。其复杂度为 O(p x。导致的误差并不很大 n ma)且￣的影响算法的正确性 .而其计算复杂度减小为 0

分解成相对比较小的问题 .些较小的问题一般都可这

以解决.并且利用了最优子结构 .由下向上的方法从子问题的最优解一步一步地构造出整个问题的最优解。

动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态参量的设置 .就是说 . 也从

初始状态到最终状态要经过多个过程.经历不同的状态，断地根据上一步状态决定下一状态，从而形成不

(2m x 2,以证明相对误差为：:一 np a/ k可 ) r( P e

,其

了一个决策序列 .最终将整个问题解决。这就是典型

中P和 P分别为优化算法和近似算法的价值，它们限制在((k1/ma n2 )p x的数量内如果我们期望相对 - )误差最大值 e 0此时复杂度为 On )>, ( Ve。

琨

的多段决策的特性在利用动态规划思想解决 0 1背包问题时 .—可

代 看计以将整个物品放到背包的过程 .成一 …… 此处隐藏：7864字，全部文档内容请下载后查看。喜欢就下载吧 ……