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 ",ans(0.5,n,k)); 40 } 41 return 0; 42 }