0/1背包问题是一种特殊的背包问题,装入背包的物品不能分割,只允许或者整个物品装入背包,或者不装入,即xi=0,或1,(0<=i
首先,选择最优量度标准为收益重量比;其次,依据收益重量比的非增次序对输入(物品)进行排序(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3)对物品排序结果为:4,0,5,2,6,1,3最后,进行贪心选择,求得的0/1背包问题的最优解为x=(1,0,1,0,1,1,1);即装入第0,2,4,5,6物品最大收益:P=52但实际上,当y=(1,1,1,0,1,1,0)即装入第0,1,2,4,5物品,可获收益为P=54,所以,贪心法求得的0/1背包问题的解x一定不是最优解.原因是:对于0/1背包问题,贪心法并不能保证使其单位载重下的收益最大,因为通常在背包没还装满时,却再也装不下任何物品,这样,就使得单位载重下的物品收益减少,所以,0/1背包问题通常不能用贪心法求解
举一反三
- 【单选题】背包问题: n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是()。 A. 重量小的优先装入背包 B. 体积小的优先装入背包 C. 价值大的优先装入背包 D. 单位重量的价值大的优先装入背包
- 部分背包问题，背包容量c=20 ，物品1，2...n, 对应的物品价值p =[4, 8，15, 1, 6，3], 对应的物品重量w=[5, 3，2, 10, 4, 8]，求装入背包的最大价值和装入物品。（1）该问题最好使用（）算法求解。A 枚举B 贪心C 分治D 递推（2）装入背包的最大价值是_____（3）装入背包的最大价值对应的完整物品是____、____、____、____。(编号从小到大）
- 用回溯法解决0-1背包问题时，对于左子树【装入物品】而言，剪枝条件是( )。 A: 得到一个可行解 B: 得到一个最优解 C: 当前物品不能装入背包 D: 当前物品能装入背包
- 0-1背包问题：给定n种物品和一背包，物品i的重量wi，价值vi，背包容量为c，如何选择装入背包中的物品，使得装入背包中的物品总价值最大。设m[i][j]是前i个物品装入背包容量为j的背包所能获得的最大价值，下面是关于最优值的递归定义，从中选出正确的关于最优值m[i][j]的递归定义。[/i][/i] 未知类型：{'options': ['', '', '', ''], 'type': 102}
- {给定n种物品和一背包,物品i的重量是wi,其价值为vi,背包的容量为C,物品不能拆分,问应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?设计解决该问题的动态规划算法的递归关系;写出该算法,并在关键处加以注释。}
内容
- 0
背包问题，背包容量C=20 ，物品价值p =[4, 8，15, 1, 6，3], 物品重量w=[5, 3，2, 10, 4, 8]， 如果是0-1背包问题，求装入背包的最大价值和相应装入物品。(1)该问题最好使用（）算法求解？A 动态规划算法B 贪心算法C 枚举算法D 分治算法(2)装入背包的最大价值是_____,(3)最大价值对应的物品编号为____、____、____、____。
- 1
设有载重能力M=20的背包和3件物品0、1、2的重量为：（w0，w1，w2）=(18，15，10)，物品装入背包的收益为：（p0，p1，p2）=(25，24，15)，用贪心算法求解该背包问题。
- 2
背包问题,背包容量C=20,物品价值p=[4,8,15,1,6,3],物品重量w=[5,3,2,10,4,8].如果是0-1背包问题,求装入背包的最大价值和相应装入物品。该问题最好使用(___)算法求解.装入背包的最大价值是(_____),对应的完整物品是(____)、(____)、(____)、(___)。 [br][/br] 如果物品数为n,算法的时间复杂度为O()。
- 3
如果从最后一个物品开始装入背包，0-1背包问题的最优解为( )。【n为物品数量，c为背包容量】
- 4
如果从第一个物品开始装入背包，在能够装入的情况下，背包的最优价值m[i][j]=( )。