描述:
有n个物品,单个物品的质量为w(weigh),价值为v(value),要从n个物品中选取k个,求再所有的选取方案中,能获得的最大单位质量价值。也就是k个物品总的价值V / 总的质量W。保留两位小数。
说明:
一般最先想到的方法是把每个物品按照单位价值排序,从大到小贪心进行选取。但这种方法是不正确的。举一个反例就好了。
比如说:n = 3, k = 2,(w, v) = {(2,2),(5,3),(2,1)},按照之前的策略应该选第一和第二物品,得到的平均价值为5/7 = 0.714。
但如果我们选择第一和第三个物品的话,结果就是3/4 = 0.75。所以说要想别的办法......
阅读全文