首页 > 代码库 > NYIST 914 Yougth的最大化

NYIST 914 Yougth的最大化

2024-07-23 18:45:27   221人阅读

Yougth的最大化
时间限制：1000 ms | 内存限制：65535 KB
难度：4


描述

Yougth现在有n个物品的重量和价值分别是Wi和Vi，你能帮他从中选出k个物品使得单位重量的价值最大吗？

 

输入

有多组测试数据,每组测试数据第一行有两个数n和k，接下来一行有n个数Wi和Vi。(1<=k=n<=10000) (1<=Wi,Vi<=1000000)


输出
输出使得单位价值的最大值。（保留两位小数）


样例输入
3 2
2 2
5 3
2 1


样例输出
0.75


来源
Yougth


上传者
TC_杨闯亮

解题：01分数规划

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <cstdlib> 6 #include <climits> 7 #include <vector> 8 #include <algorithm> 9 #include <cmath>10 #include <sstream>11 using namespace std;12 const double exps = 1e-3;13 struct xyz {14     int w,v;15     double c;16 } p[10010];17 inline bool cmp(const xyz &a,const xyz &b) {18     return a.c > b.c;19 }20 double ans(double t,const int &n,const int &k) {21     int i,a = 0,b = 0;22     double q = 0.0;23     for(i = 0; i < n; i++)24         p[i].c = p[i].v - t*p[i].w;25     sort(p,p+n,cmp);26     for(i = 0; i < k; i++) {27         a += p[i].v;28         b += p[i].w;29     }30     q = a*1.0/b;31     if(fabs(q-t) < exps) return q;32     return ans(q,n,k);33 }34 int main() {35     int n,k,i;36     while(~scanf("%d %d",&n,&k)) {37         for(i = 0; i < n; i++)38             scanf("%d %d",&p[i].w,&p[i].v);39         printf("%.2f\n",ans(0.5,n,k));40     }41     return 0;42 }
View Code

 

NYIST 914 Yougth的最大化


联系
我们