您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 分支限界搜索 >

分支限界法解决01背包问题

发布时间:2019-08-11 14:52 来源:未知 编辑:admin

  设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1= i =n)装入背包,则有价值为pi . 目标是找到一个方案, 使得能放入背包的物体总价值最高.

  ②A为当前扩展结点,其儿子结点B和C均为可行结点,将其按从左到右顺序加入活结点队列,并舍弃A。

  ③按FIFO原则,下一扩展结点为B,其儿子结点D不可行,舍弃;E可行,加入。舍弃B

  ⑤扩展结点E的儿子结点J不可行而舍弃;K为可行的叶结点,是问题的一个可行解,价值为45

  ⑥当前活结点队列的队首为F, 儿子结点L、M为可行叶结点,价值为50、25

  ①用一个极大堆表示活结点表的优先队列,其优先级定义为活结点所获得的价值。初始为空。

  ⑥E的儿子J是不可行叶结点,舍弃。K是可行叶结点,为问题的一个可行解价值为45。

  ⑧算法搜索得到最优值为50,最优解为从根结点A到叶结点L的路径(0,1,1)。

  应用贪心法求得近似解为(1, 0, 0, 0),获得的价值为40,这可以作为0/1背包问题的下界。

  如何求得0/1背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第1个物品且可以将背包装满,则可以得到一个非常简单的上界的计算方法:

  ①在根结点1,没有将任何物品装入背包,因此,背包的重量和获得的价值均为0,根据限界函数计算结点1的目标函数值为10×10=100;

  ②在结点2,将物品1装入背包,因此,背包的重量为4,获得的价值为40,目标函数值为40 + (10-4)×6=76,将结点2加入待处理结点表PT中;在结点3,没有将物品1装入背包,因此,背包的重量和获得的价值仍为0,目标函数值为10×6=60,将结点3加入表PT中;

  ④在结点4,将物品2装入背包,因此,背包的重量为11,不满足约束条件,将结点4丢弃;在结点5,没有将物品2装入背包,因此,背包的重量和获得的价值与结点2相同,目标函数值为40 + (10-4)×5=70,将结点5加入表PT中;

  ⑥在结点6,将物品3装入背包,因此,背包的重量为9,获得的价值为65,目标函数值为65 + (10-9)×4=69,将结点6加入表PT中;在结点7,没有将物品3装入背包,因此,背包的重量和获得的价值与结点5相同,目标函数值为40 + (10-4)×4=64,将结点6加入表PT中;

  ⑧在结点8,将物品4装入背包,因此,背包的重量为12,不满足约束条件,将结点8丢弃;在结点9,没有将物品4装入背包,因此,背包的重量和获得的价值与结点6相同,目标函数值为65;

  ⑨由于结点9是叶子结点,同时结点9的目标函数值是表PT中的极大值,所以,结点9对应的解即是问题的最优解,搜索结束。

  ★也可将上界函数确定的每个结点的上界值作为优先级,以该优先级的非增序抽取当前扩展结点。由此可快速获得最优解。

http://gamesbaby.net/fenzhixianjiesousuo/730.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有