试题详情
简答题 假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M=150，使用回溯方法求解此背包问题。请写出状态空间搜索树并计算各个节点处的界限函数值，最后给出装载方案及背包中物品的重量和价值。
  • 按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：


    在Q1处获得该问题的最优解为（1，1，1，1，0，0，1），背包效益为170。即在背包中装入物品F，B，G，D，A时达到最大效益，为170，重量为150。

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

热门试题