试题详情
简答题假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。
  • 贪心算法：
    （1）标准：重量、价值和单位价值。
    （2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。
    使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。
    使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。
    （3）显然使用单位价值作为标准得到的是最优解。
    回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：


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

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

热门试题