程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ Yougth的最大化

NYOJ Yougth的最大化

編輯:C++入門知識

NYOJ Yougth的最大化


 

 

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

 

 

/*
 *二分搜索+貪心選擇 
 *二分搜索:首先,你得知道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; 
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved