单选题 适中
#22012

一个0-1背包问题,背包容量为20,现有5个物品,重量和价值分别为7,5,4,3,6和15,12,9,7,13,装入背包的物品能获得的最大总价值是多少?

一个0-1背包问题,背包容量为20,现有5个物品,重量和价值分别为7,5,4,3,6和15,12,9,7,13,装入背包的物品能获得的最大总价值是多少?

未登录也能判分,登录后才会记录
答案与解析
正确答案:D
解析

0-1背包中物品要么选要么不选,分类讨论:  

装5个物品:总重量25>20,不合法;  

装4个物品:移走一个物品使总价值最大,选重量3、4、6、7的物品,价值和7+9+13+15=44;  

装3个物品:价值最大的3个物品价值和40<44。