试题详情
简答题 对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。
  • 物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物品3的单位重量价值为30元/千克。采用贪心算法解此背包问题。
    此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品2，然后是物品1，最后是物品3，直至将背包装满。
    物品2全部装入背包，当前背包中价值120元，背包占用20千克，剩余30千克；
    物品1全部装入背包，当前背包中价值220元（120元＋100元），背包占用40千克，剩余10千克；
    物品3的1/3被装入背包，当前背包中价值250元（120元＋100元＋90元×1/3），背包占用50千克（装满）。
    因此，最终装入背包的最大价值为250元，物品1和物品2都全部装入，分别是20千克和20千克，物品3装入1/3，是10千克。

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

热门试题