简答题

有0-1背包问题如下: n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。 其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量。请问对于此0-1背包问题,应如何选择放进去的物品,才能使到放进背包的物品总价值最大。 P=(15,8,6,4,3,1),W=(2,3,4,5,8,10),单位重量物品价值(7.5,2.67,1.5,0.8,0.375,0.1)

正确答案

可知随着物品的重量增加,物品的价值减少;因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包,此时剩余载重量为17,P为15。
2.把重量为3的物品放进背包,此时剩余载重量为14,P为23;
3.把重量为4的物品放进背包,此时剩余载重量为10,P为29;
4.把重量为5的物品放进背包,此时剩余载重量为5,P为33;
由于8>5,所以不能再放进背包。
结果是把重量为2,3,4,5的物品装进背包,总价值最大为33。

答案解析

相似试题
  • 有这样一类特殊0-1背包问题:可选物品重量越轻的物品价值越高。 n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。 其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量。请问对于此0-1背包问题,应如何选择放进去的物品,才能使到放进背包的物品总价值最大,能获得的最大总价值多少?

    简答题查看答案

  • 用动态规划算法解0-1背包问题:n=5,w=[2,9,4,6,7],p=[6,10,12,8,13],c=15。

    简答题查看答案

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

    简答题查看答案

  • 请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20,15,10},价值为{20,30,25},背包容量为25时搜索空间树。

    简答题查看答案

  • 考虑背包问题:n=6,物品重量W=(1,5,2,3,6,1),价值P=(15,59,21,30,60,5),背包载重量C=10。能放进背包的物品价值最大为()。

    单选题查看答案

  • 对于如下描述的背包问题,请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量:C=50千克。3件物品。物品1重20千克,价值100元;物品2重20千克,价值120元;物品3重30千克,价值90元。

    简答题查看答案

  • 使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是(),只使用约束条件进行裁剪的是()。

    填空题查看答案

  • 对于0-1背包问题和背包问题的解法,下面()答案解释正确。

    单选题查看答案

  • 关于0-1背包问题以下描述正确的是()

    单选题查看答案