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
#include<stdio.h>
#include<algorithm>
#define MAX(x,y) x>y?x:y
using namespace std;
const int MAXN=;
struct Node{int v,w;
};
Node res[MAXN];
double cont[MAXN];
int n,k;
int fun(double mid){//大神们都说这是0-1分数规划。。。
for(int i=;i<n;i++){
cont[i]=res[i].v-mid*res[i].w;
}
sort(cont,cont+n);double sum=;
for(int i=n-;i>=n-k;i--)sum+=cont[i];//从大到小代表k个物品使得单位重量的价值最大
//printf("%lf\n",mid);
return sum>=?:;
}
double abs(double x){
return x>?x:-x;
}
double search(double max){//二分查找
double left=,right=max,mid;
while(right-left>1e-){mid=(left+right)/;
if(fun(mid))left=mid;
else right=mid;
}
return mid;
}
int main(){
while(~scanf("%d%d",&n,&k)){double max=;
for(int i=;i<n;i++){
scanf("%d%d",&res[i].w,&res[i].v);
max=MAX(max,res[i].v*1.0/res[i].w);//醉了，少了个MAX错了无数次；；；；
}
printf("%.2f\n",search(max));
}
return ;
}