数学执车与率用
精确算法求解多维背包问题
黄林峰
(淄博职业学院信息工程系山东淄博255314)
算法分析
摘要：骨包问题自提出以来引起学者广泛研究,积累了许多优秀求解算法。精确求解算法主要有动态规列法和分校限法,这费算法能精确得到问题的解。虽然精确算法不宜用来直接求解大规模问题，但仍有大量性能优秀的求解肾包同题的精确算法。达些算法通常会将问题分割成若干规模不大的子问题，在对子问题用动态规划等精确算法求解，以得到问题较好的解。
关键词：多维肾包同题动态规划分被限界法
中图分类号：0221.4 1多维背包问题简介
文献标识码：A
MKP(MultidimensionalKnapsack Problem)被称为多维背包问题，也叫多约束背包问题。MKP较单约束背包问题不同在于每个物品消耗的资源并不是单一的。在单约束背包问题中，物品只消耗一个资源属性，即重量，物品的装人只受重量的约束，面在多约束背包问题中，物品有多个消耗属性，比如重量，体积等等，物品的装
入就变得更加复杂。 2精确算法求解
精确算法在解决小规模的背包问题时很有优势，它们可以在可以接受的时间内找到间题的最优解。精确算法主要有两类：动态规划和分枝限界。
(A)动态规划法。动态规划最初由bellman等人创建。Morin引入以解决背包问题。动态规划在寻找问题的最优解时会构造多个子状态，利用最优性原理以及递推关系式寻找最优序列，最优性原理的内客是，过程的最优决策序列必须满是如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构造一个最优决策序列，
对KP：定义pli，w)为已经考患了第i个物品已经装入w的约束时得到的最大价值，则Ⅱ，c为最大价值.递推关系式为
ww[-1] p[i,w}mex( p[-1,w]p[-1,ww[i}[i]
wow[i-1]
p[i,wFp[i-1,w]
(1)(2)
对MKP：i为物品标号，g为m维约束，Ai为第i个物品的m维约束，
Ci为第i个物品的价值。
f[i,g]=max ( f[i-1,g], f[i-1,g-Ai]+Ci 1
(3)
直接用动态规划法解决背包问题主要缺点是搜索空间太大。动态规划是一种隐枚举方法，它在构造问题最优解时会构造出问题的所有可行解，这对于一般的问题计算量就非常大了。考虑一个物品数量为100，约束为2，每维约束为1000的MKP问题，动态规划的计算量为100×1000×1000，因此动态规划不宜用来直接求解大规模问题。
虽然动态规划方法有许多不足，但在仍有大量性能优秀的基于动态规划求解背包问题的算法。这些算法通常会将问题分割成若干规模不大的子问题，在对子间题用动态规划求解，以得到问题较好解。
收移日期：2015-11-19
文章编号:1007-9416(2015)12-0145-01
(2)分枝限界法。分枝限界法(Brenchandboundmethod)最初在六十年代由Dakin等人提出，用于解决整数规划间题。它用一个分枝和一个限界操作来缩小问题的搜索空间。
Horowitz和sahni首先利用分枝限界解决KP间题。Shih首次利用分枝限界解决MKP问题。另一个用于解决MKP问题的改进分枝限界算法由Gavish和Pirkul提出，用分枝限界法求解问题时都要求得当前决策可以产生的目标上界，背包间题的上界一般通过松弛原问题得到。在文献[2]中，作者比较了MKP的三种松弛方式： Lagrangean松驰(Lagrangean relaxation)，代理松弛(Surrogate relaxation)，混合松驰(compositerelaxation)，试验数据显示这些松得到的上界比用线性规划(linearprogrammingrelaxation) 更紧致，作者利用分枝限界法，用混合松弛求得上界，并将实验数据
同shih比较，结果显示算法运行时间更短，结果更优。 3结语
背包问题是NP难问题，也是复杂性研究和算法研究的热点间题。精确算法在解决小规模的背包问题时很有优势，它们可以在能
接受的时间内找到问题的最优解。参考文献
[1JB.Gavish and H.Pirkul,"Efficient algorithm for solving the multiconstraint zeroone knapsack problem to optimality". Math.Programming.vo1.31.pp.78105,1985.
[2JParraHernandez and Dimopoulos,A new heuristic for solv-ing the multichoice multidimensiona1 knapsack problem",IEEE Transactions on Systems,Man and CyberneticsPart A:Systems and Humans,vo1.35,pp.708717,2005.
作者简介：黄林峰(1981一),男,汉族,山东烟台人,毕业于中国科技大学,现就职于满博职业学院,研究生,制教投,研究方向：进化计算、智能
信息处理等。
145