BZOJ5281: [Usaco2018 Open]Talent Show（01分数规划&DP）

5281: [Usaco2018 Open]Talent Show

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 166 Solved: 124
[Submit][Status][Discuss]

Description

FarmerJohn要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第i头奶牛重

量为wi，才艺水平为ti，两者都是整数。在到达时，FarmerJohn就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为W

（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够

达到的最佳的才艺与重量的比值。

Input

输入的第一行包含N和W。下面N行，每行用两个整数wi和ti描述了一头奶牛。

1≤N≤250

1≤W≤1000

1≤wi≤10^6

1≤ti≤10^3

Output

请求出Farmer用一组总重量最少为W的奶牛最大可能达到的总才艺值与总重量的比值。

如果你的答案是A，输出1000A向下取整的值，以使得输出是整数

（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

Sample Input

3 15
20 21
10 11
30 31

Sample Output

1066
在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛，但是由于我们需
要至少15单位的重量，最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值
为(11+21)/(10+20)=32/30=1.0666666...，乘以1000向下取整之后得到1066。

思路：分子分母的最大形式显然需要二分后01分数规划求最大。二分到mid的时候，我们按照t-w*mid排序。这个时候出现问题了，我们是选择最前面几个直到体积大于等于W吗，显然不是的。比如需要体积W=120的东西，现在有三种（w，t）：（100，100），（70，35），（20，9）；显然选择1，3的比值比选择1，2搞，尽管2的性价比比3高。主要是因为我们只需要W=120，2的性价比虽然高于3，但是无用的w也多了，拉低了整体性价比。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

struct in{

    int w,t; double xjb;

    friend bool operator <(in w,in v){ return w.xjb>v.xjb; }

}s[maxn];int N,W; double dp[maxn];

bool check(double Mid)

{

    for(int i=;i<=N;i++) s[i].xjb=(double)s[i].t-Mid*s[i].w;

    sort(s+,s+N+);

    for(int i=;i<=W;i++) dp[i]=-1000000000.0; dp[]=0.0;

    for(int i=;i<=N;i++){

        for(int j=W;j>=;j--){

            if(j+s[i].w>=W){

                if(dp[j]+s[i].xjb>=) return true;

            }

            else dp[j+s[i].w]=max(dp[j+s[i].w],dp[j]+s[i].xjb);

        }

    }

    return false;

}

int main()

{

    scanf("%d%d",&N,&W);

    for(int i=;i<=N;i++) scanf("%d%d",&s[i].w,&s[i].t);

    double L=,R=1000000.0,Mid,ans=; int num=;

    while(num--){

        Mid=(L+R)/;

        if(check(Mid)) L=Mid,ans=L;

        else R=Mid;

    }

    printf("%d\n",(int)(ans*));

    return ;

}

秒客网