0—1背包问题的多重分枝—限界算法.pdf.pdf

维普资讯
第卷第期武汉驯绘科技太学学报..
『年月。
一%一背包问题的多重分枝一限界算法
⋯⋯婢⋯⋯。//.
. ‘武科科与”一
摘要建立了背包问题数学模型的一般形式,对通常的分桂一限界算法作了推广,给出了多重
分枝一限界算法,,可用:解决某些具有“多重”性质的
关键词苎塾必:萱包分枝一限界算法每哮历/锣曼像覆、
分类号】. /
—背包问题的多重分枝一限界算法
. 数学模型
多背包的一背包问题的数学模型如下:
设有个背包,它们能容纳的重量分别为, 一,Ⅳ有“个物品,称为物品,,⋯,,
它们的重量分别为, ”,.,将它们装入背包所取得的效益分别为,肌,⋯, 。变量
表示将物品装入背包,一表示物品不装入背包。目标函数为:
『●
∑∑

约束条件为∈,, ∑正≤, ∑. ≤
’一一
≤≤“, ≤≤
据此确定使目标函数取最大仿的%值。
. 算法的基本思想
下面结合字铡说明多重分枝一限界算法的基本思想
设有两个背包,分别称为背包和背包,它们能容纳的重量分别为一, : 。今
有个物品,其重量分别为一, 一, .. ;各物品放入背包所获得的效益分别
为, , , 。需将物品装入两个背包对每个物品不允许部分装入背包,使
取得的效益最大。
对应每个背包,各有一棵状态空间树,树的结点代表物品装入背包的状况与本实例对应
的状态空问树见图和图,两憬树的高度都是一是物品个数,树中结点按宽度优先原则
生成。将两棵树中任意一棵确定为主树,则另一棵称为副树只有主树的叶结点才可能是解状
态,而答案状态是解状态中使目标函数取最大值的叶结点。设对应背包的状态树是主树,对
应背包的状态树是副树,并假定”个物品已按单位重量效益的非增次序排序;
./ ≥⋯/, ≤‘≤一
从主树的恨结点开始,它是当前被扩展结点称为结点计算根结点处效益的下界
收璃日期,一李鸣山,,现从事人工智能算法理论研究
维普资讯
武汉测绘科技大学学报
一. 、
. . .
, , 、、
¨ 】: / 一卜
⋯. / 、
~
.
\
。。\ \ ’
一. .
’/ 、‘⋯三。
, ‘。
、。\ 一
声器‘、
Ⅵ:
㈣
. : 蒜
一转副、, , 逅阿
~ .
,,』】“.
田主树田副树
和上界,计算的方法在中说明。根结点处的值作为计算全过程的效益下界
的初值。
生成根结点的两个子结点——左子结点和右子结点,它们分别表示将物品放入背包
和不放入背包。。并将它加
;否则不生成左子结点。对右子结
点,它总是可行的。先计算它的和值,如果效益上界,则扩展右子结点不
可能导致最优解,它立即被杀死;否则将右子结点加入活结点表,并以与中较大者作
为新的值。
在活结点表中选取值最大的结点作为结点,对它的两个子结点的处理与
相同。而刚才作为结点的活结点则从活结点表中删除,因为它的子结点都已生成,对找最优
解来说,它已没有存在的必要了。
上