一个背包问题变种（纯贪心）有一个最多能用m公斤的背包,现在有n种物品,每件的重量分别是W1,W2,...,Wn,物品能够分割（就是直接算单位重量）每件的价值分别为C1,C2,...,Cn.若的每种物品的件数

Question

一个背包问题变种（纯贪心）
有一个最多能用m公斤的背包,现在有n种物品,每件的重量分别是W1,W2,...,Wn,物品能够分割（就是直接算单位重量）
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值.
DEP C
.说错了,每件物品最多只能取两件

Answer 1

先计算出每件物品的单位重量的价值是s,s即是（Ci/Wi).
然后写一个快速排序qsort,从大到小排序.
然后逐个计算添加进去即可,直到达到背包重量m即可.
记得hdu上有一道题就跟楼主的意思差不多,太久之前的,也记得不太清楚.