首页 > 其他 > 详细

【深基12.例1】部分背包问题

时间:2020-07-22 18:53:27      阅读:55      评论:0      收藏:0      [点我收藏+]

https://www.luogu.com.cn/problem/P2240

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, t;
 4 struct jb{ //金币结构体 
 5     int m, v;//重量,价值 
 6 };
 7 jb a[105];//用于存储n 堆金币 
 8 double ans;//记录答案可以拿走金币总价值 
 9 bool cmp(jb x, jb y){//排序参数设定:单位重量金币价值 
10     return x.v*1.0/x.m > y.v*1.0/y.m;//注意数据类型的转换 
11 }
12 int main()
13 {
14     cin>>n>>t;
15     for(int i=0; i<n; i++)     //输入n堆金币 
16         cin>>a[i].m>>a[i].v;
17     sort(a, a+n, cmp);         //按单位重量金币价值从大到小排序    
18     for(int i=0; i<n; i++){
19         if(t>=a[i].m){         //背包剩余重量 和 当前堆金币重量比较 
20             ans+=a[i].v*1.0;
21             t-=a[i].m;
22         }
23         else{                 //背包剩余量装不下时,分割金币装包 
24             ans+=a[i].v*1.0/a[i].m*t;
25             t=0;
26         }
27         if(t==0)break;        //背包剩余量为 0时结束装包 
28     }
29     cout<<fixed<<setprecision(2)<<ans;
30     return 0;
31  } 

 

【深基12.例1】部分背包问题

原文:https://www.cnblogs.com/tflsnoi/p/13362304.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!