努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！
题目描述
有n种物品，每种物品只有一个，第i种物品的重量为 wi，价值为 vi，背包的容量为 w，物品可以分割。如何放置物品，使装入背包的物品价值之和最大?
问题分析
（1）每次选择价值最大的物品装入背包。
（2）每次选择重量最小的物品装入背包。
（3）每次选择单位重量价值最大的物品转入背包。
思考一下，如果选价值最大的物品，但重量非常大，则可能一个也装不下，分割一部分装入，价值未必是最高的；如果选重量最小的物品装入，则其价值不一定高，所以在总重量受到限制的情况下无法保证价值最大；而如果每次选单位重量价值最大的物品，则装满背包后一定能得到最大价值。
因此，我们应采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。
算法设计
（1）确定合适的数据结构并初始化。首先将物品的重量、价值和单位重量价值定位为一种结构体类型，然后对物品按单位重量价值从大到小进行排序。
（2）根据贪心策略，按照单位重量价值从大到小选取物品，直到达到背包容量。如果在装入第 i 个物品时超出背包容量，则取该物品的一部分装入背包。
完美图解
物品的价值和重量如表2-3所示。如果背包容量 w = 30，怎么才能装入最大价值的物品？
物品清单
| 物品 i3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 重量 w[i] | 4 | 2 | 9 | 5 | 5 | 8 | 5 | 4 | 5 | 5 |
| 价值 v[i] | 3 | 8 | 18 | 6 | 8 | 20 | 5 | 6 | 7 | 15 |
（1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降序排列，排序后的物品清单如下所示：
排序后的物品清单
| 物品 i | 2 | 10 | 6 | 3 | 5 | 8 | 9 | 4 | 7 | 1 |
| 重量 w[i] | 2 | 5 | 8 | 9 | 5 | 4 | 5 | 5 | 5 | 4 |
| 价值 v[i] | 8 | 15 | 20 | 18 | 8 | 6 | 7 | 6 | 5 | 3 |
| 单位重量价值 | 4 | 3 | 2.5 | 2 | 1.6 | 1.5 | 1.4 | 1.2 | 1 | 0.75 |
（2）按照贪心策略，每次选择单位重量价值大的物品装入背包。
（3）构造最优解
算法详解
（1）确定合适的数据结构。
struct node { double w; //每种物品的重量 double v; //每种物品的价值 double p; //每种物品的单位重量价值（价值/重量） }
（2）对物体按单位重量价值进行排序。
bool cmp(node a, node b) { //自定义比较函数cmp return a.p > b.p; // 指定按照物品的单位重量价值进行降序排列 } sort(s, s + n, cmp); //前两个参数分别为待排序数组的首地址和尾地址，cmp为比较函数
（3）使用贪心算法求解问题
double solve (int n, double w) { double sum = 0.0; //sum表示已经装入物品的价值之和 double cleft = w; //背包的剩余容量 for(int i = 0; i < n; i++) { //是用贪心算法求解问题 if(s[i].w < cleft) { //如果物品的重量小于或等于剩余容量 cleft -= s[i].w; sum += s[i].v; } else { //如果物品的重量大于剩余容量 sum += cleft * s[i].p; //部分装入 break; } } return sum; }
算法分析
（1）时间复杂度：时间主要耗费在对物品按单位重量价值进行排序上，一般采用快速排序法，时间复杂度为O(nlogn)。
（2）空间复杂度：空间主要消耗在存储物品的单位重量价值上，空间复杂度为O(n)。
