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分数规划
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
const double exps = 1e-;
struct xyz {
int w,v;
double c;
} p[];
inline bool cmp(const xyz &a,const xyz &b) {
return a.c > b.c;
}
double ans(double t,const int &n,const int &k) {
int i,a = ,b = ;
double q = 0.0;
for(i = ; i < n; i++)
p[i].c = p[i].v - t*p[i].w;
sort(p,p+n,cmp);
for(i = ; i < k; i++) {
a += p[i].v;
b += p[i].w;
}
q = a*1.0/b;
if(fabs(q-t) < exps) return q;
return ans(q,n,k);
}
int main() {
int n,k,i;
while(~scanf("%d %d",&n,&k)) {
for(i = ; i < n; i++)
scanf("%d %d",&p[i].w,&p[i].v);
printf("%.2f\n",ans(0.5,n,k));
}
return ;
}