描述：

       这里有n种不同值v[i]和权重w[i]的对象（如果选择该对象的w[i]可以获得值v[i]）。

　　你有一个容器来挑选它们。你可以根据自己的需要把它们分成任意大小的碎片。可以拾取的对象的最大重量给定为w。请计算您能得到的最大值。

输入：

       第一行输入n W（0<=n<=1000）（0<=W<=10000）

       第二行输入n个物品的价值（0<=v[i]<=10000）

　　第三行输入n个物品的质量（0<=w[i]<=10000）

输出：

       最大的价值，保留三位小数。

分析：

　　本题跟传统的0-1背包问题不同，本题中的物体可以分成任意份，所以我们可以运用贪心算法，根据物品的性价比（价值 / 质量）来解题，根据性价比的高低依次将物体放入背包中，当物体不能完全放入背包时，总价值 =   完全放入物品的价值 +  背包剩余空间 * 接下来应放入背包物品的性价比。

代码：

#include 
#include 
#include
using namespace std;//需要一个结构体，通过性价比，能够查找到重量和价值。
//做一个排序，需要将性价比由高到底排序，排序的过程中重量和（价值）要对应上typedef struct {double aver;double w;double v;
}Knapsack;bool cmp(Knapsack a, Knapsack b)
{return a.aver > b.aver;
}
int main()
{Knapsack arrays[1009];int n;double m;double V = 0;cin >> n >> m;for (int i = 0; i < n; i++)cin >> arrays[i].v;for (int i = 0; i < n; i++)cin >> arrays[i].w;//求性价比for (int i = 0; i < n; i++){arrays[i].aver = arrays[i].v / arrays[i].w;//cout << arrays[i].aver << endl;}//性价比排序sort(arrays, arrays + n, cmp);int sum = 0;for (int i = 0; i < n; i++)  //当背包能装下所有物品时，直接输出所有的物品价值之和{sum += arrays[i].w;}if (sum < m){for (int j = 0; j < n; j++)V += arrays[j].v;//V = floor(V * 1000.0) / 1000.0;cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;return 0;}//应该由性价比的顺序，通过容量，选择装入的物品for (int i = 0; i < n; i++) {if (arrays[i].w <= m){V = V + arrays[i].v;m = m - arrays[i].w;}else {//直接将剩余的m加入即可V = V + m * arrays[i].aver;m = 0;}if (m == 0)break;}//V = floor(V * 1000.0) / 1000.0;cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;return 0;
}