分支限界---->0/1背包
分支限界---->0/1背包
小强斋太 发表于1年前
分支限界---->0/1背包
  • 发表于 1年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

0-1背包问题

一、优先级如何确定?

在优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。

二、分支限界算法思想

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

 

共有 人打赏支持
粉丝 0
博文 181
码字总数 0
×
小强斋太
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: