试题详情
简答题 考虑用分支限界解0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 示例：n=3，C=30，w={16，15，15}，v={45，25，25} 求： 1、问题的解空间树 2、约束条件 2、如何剪枝？
  • 问题的解空间树：

    约束条件：
    如何剪枝：
    设r是当前尚未考虑的剩余物品价值总和；Cv是当前价值；bestv是当前最优价值。
    当r＋Cv≤bestv时，可剪去右子树。

  • 关注下方微信公众号，在线模考后查看

热门试题