小数背包

2018/08/01 10:57
阅读数 231

题目描述

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

 

输入

第1行有两个数,M和N;
第2行到N+I行:第i行为第i-1个物品的价值和质量(均为小于100的正整数),中间用空格隔开。

 

输出

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

 

样例输入

150 7
10 35
40 30
30 60
50 50
35 40
40 10
30 25

 

样例输出

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\n",ans);
43     return 0;
44 }
View Code

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部