?

?

Yougth的最大化

描述

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

?

?

/*
 *二分搜索+贪心选择 
 *二分搜索：首先，你得知道k个（任意个）物品的单位价值不超过的最大的单个物品的单位价值，自己想想就明白了  
 *          所以ans（假定为最终答案）必定在0-最大单个物品的单位价值之间，我们可以用二分法来不断缩小区间范围
            直至精度达到要求。至于如何决定区间范围是往左边还是往右边缩小，就需要对当前答案进行判断，判断是否存在一种方案
            可以使得k个物品的单位价值不低于当前答案，判断方案存在与否需要用到贪心选择                                                                                          
 *贪心选择：(v1+v2+...+vk)/(w1+w2+...+wk)>=cur_ans(即当前答案) 
 *          将这个式子转化成：(v1-cur_ans*w1) + (v2-cur_ans*w2) + .. (vk-cur_ans*wk) >= 0
 *          至此，可以看出我们可以对vi-cur_ans*wi组成的数组进行非递增排序，选出前k个作为方案 
 */ 

#include 
      
       
using namespace std;
#include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define eps 1e-3 #define MAXN 10005 int n,k; double v[MAXN],w[MAXN]; int check(double x) { double a[MAXN]; for (int i = 0; i < n; ++i) { a[i] = v[i] - x*w[i]; } sort(a,a+n); reverse(a,a+n); double sum = .0; for (int i = 0; i < k; ++i) { sum += a[i]; } return (sum >=0) ? 1 : 0; } double fenzhi(double right) { double l = 0, r = right; while (r - l > eps) { double mid = (l+r)/2; if (check(mid)) { l = mid; } else { r = mid; } } return l; } int main() { while (cin >> n >> k) { double right = -1; for (int i = 0; i < n; ++i) { cin >> w[i] >> v[i]; right = max(right,v[i]*1.0/w[i]); } printf(%.2lf ,fenzhi(right)); } return 0; } 
           
          
         
        
       
      

?

?