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 epu 1e-3 using namespace std; void result(); bool greddy(double mid); int n,c; struct Data{ double vi; double wi; }a[10005]; double sum[10005]; double m; int main() { double vi,wi; int i; while(scanf("%d%d",&n,&c)!=EOF) { m=0.0; for(i=0;i<n;i++) { scanf("%lf%lf",&a[i].wi,&a[i].vi); if(a[i].vi/a[i].wi>m) m = a[i].vi/a[i].wi; } result(); } return 0; } void result() { double left=0.0; double right=m; double mid; // while(right-left>epu) // { // mid=(right+left)/2; // if(greddy(mid)) // left=mid; // else // right=mid; // } // printf("%.2lf\n",left); while(left<=right) { mid=(right+left)/2; if(greddy(mid)) left=mid+0.001; else right=mid-0.001; } printf("%.2lf\n",right); } bool greddy(double mid) { int i,j,cnt=0; double s=0.0; for(i=0;i<n;i++) sum[i]=a[i].vi-a[i].wi*mid; sort(sum,sum+n); for(i=0;i<c;i++) s += sum[n-i-1]; if(s>=0)//每个个体的价值 与 个体*单位价值 差的 和>=0时，说明找到的这个单位价值符合条件 return true; else return false; }