0-1分數規劃（nyoj914 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

題解：

Yougth的最大化

這道題目是一道0-1分數規劃求最優值。

方法是一個二分搜索+貪心的題目。

出這道題目就是告訴大家二分不僅可以查找，還可以搜索一個更優值。

要使得單位重量的價值最大，則其最大不超過單個中最大的單位重量的價值，最小當然不小於0.

那麼我們就這一在0--最大單位重量的價值中間找一個值ans，使得ans為滿足題目條件的最大值。如果滿足條件，則可以找更大的。設置一個條件。既二分搜索、

從n個物品中找k個使得k個的價值和/質量和>=ans

為了使得ans盡可能的大，那麼這裡就要貪心選擇。

代碼詳見：

 

#include 
#include 
using namespace std;
const int N = 11000;
int w[N],v[N];
double y[N];
int n,c;
int chack(double x)
{
    for(int i=0;i=0;
}
double reaerch(double enf)
{
    double l=0,r=enf,mid;
    for(int i=0;i<100;i++)
    {
        mid=(l+r)/2;
        if(chack(mid))
            l=mid;
        else
            r=mid;
    }
    return l;
}
int main()
{
    while(~scanf("%d%d",&n,&c))
    {
        double ma=0;
        for(int i=0;ima)
                ma=cmp;
        }
        printf("%.2lf\n",reaerch(ma));
    }
    return 0;
}