NYOJ Yougth的最大化

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; 
}