背包问题就是给定n种物品和一个背包 设Wi为物品i的重量 Vi为其价值 C为背包的重量容量 要求在重
已帮助 人
背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择Vi/Wi 值（价值密度）最大的物品装包。假设n=3；W1=100，V1=60；W2=20，V2=40；W3=20，V3=40；C=110。下列说法不正确的是（）
A．利用价值密度最大的贪婪准则时，选物品1，这种方案的总价值为60
B．最优解选物品为2和3，总价值为80
C．使用贪婪准则，能保证得到最优解
D．利用价值密度最大的贪婪准则时，选物品2和3，总价值为80
回答
共1条回复-
利用价值密度最大的贪婪准则时，选物品 1 ，这种方案的总价值为 60