4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1295字，纯文字阅读大概需要2分钟。

内容图文

 

• 查看
• 提交
• 统计
• 提示
• 提问

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。

输入

第一行由两个部分组成，分别为糖果箱数正整数n(1 <= n <= 100)，驯鹿能承受的最大重量正整数w（0 < w < 10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。

输出

输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束。

样例输入

4 15
100 4
412 8
266 7
591 2

样例输出

1193.0

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct T {
 4     int v,w;
 5     double p;
 6 };
 7 bool cmp(T a,T b) {
 8     return a.p>b.p;
 9 }
10 
11 int main() {
12     int n,m;
13     double ans=0;
14     cin>>n>>m;
15     T t[n];
16     for(int i=0; i<n; i++) {
17         cin>>t[i].v>>t[i].w;
18         t[i].p=t[i].v/t[i].w;
19     }
20     sort(t,t+n,cmp);
21     int i=0;
22     while(m>0) {
23         if(m-t[i].w>0) {
24             ans+=t[i].v;
25             m-=t[i].w;
26             i++;
27         }
28         else{
29             ans+=t[i].p*m;
30             m=0; 
31         }
32     }
33     printf("%.1lf\n",ans);
34     return 0;
35 }

 

内容总结

以上是互联网集市为您收集整理的4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法）全部内容，希望文章能够帮你解决4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---