小数背包

题目描述

有一个背包，背包容量是M(0<M≤500)，有N(1<N≤1000)个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

输入

第1行有两个数，M和N；
第2行到N+I行：第i行为第i-1个物品的价值和质量（均为小于100的正整数），中间用空格隔开。

输出

只有一个数为最大总价值（保留一位小数）。

样例输入

样例输出

190.6
由于物品可以被分成任意大小，我们可以用贪心来做，首先求得每个物品在单位质量下的价值，然后进行从大到小排序，最后遍历一遍，找到最后一个能放入背包的物品，如果此物品不能完全放入背包，就把它分割，用单位质量的价值乘以背包中剩余的空间，即为该物品能贡献的价值

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4 struct node
 5 {
 6     double value,weight;
 7     double p;
 8 }mp[2000];
 9 bool cmp(node x,node y)
10 {
11     return x.p>y.p;
12 }
13 int n,m;
14 int main()
15 {
16 //    freopen("in.txt","r",stdin);
17     cin>>m>>n;
18     for(int i=0;i<n;i++)
19     {
20         cin>>mp[i].value>>mp[i].weight;
21         mp[i].p=mp[i].value/mp[i].weight;
22  
23     }
24     sort(mp,mp+n,cmp);
25     double ans=0;
26     int mm=0,i;
27     for(i=0;i<n;i++)
28     {
29         mm+=mp[i].weight;
30         if(mm>m)
31         {
32             mm-=mp[i].weight;
33             ans+=(double)(m-mm)*mp[i].p;
34             break;
35         }
36         else
37             ans+=mp[i].value;
38         if(mm==m)
39             break;
40     }
41  
42     printf("%.1lf
",ans);
43     return 0;
44 }

View Code

如有错误，请指正，感谢！