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

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
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=1;i<=N;i++) s[i].xjb=(double)s[i].t-Mid*s[i].w;
    sort(s+1,s+N+1);
    for(int i=1;i<=W;i++) dp[i]=-1000000000.0; dp[0]=0.0;
    for(int i=1;i<=N;i++){
        for(int j=W;j>=0;j--){
            if(j+s[i].w>=W){
                if(dp[j]+s[i].xjb>=0) 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=1;i<=N;i++) scanf("%d%d",&s[i].w,&s[i].t);
    double L=0,R=1000000.0,Mid,ans=111; int num=100;
    while(num--){
        Mid=(L+R)/2;
        if(check(Mid)) L=Mid,ans=L;
        else R=Mid;
    }
    printf("%d\n",(int)(ans*1000));
    return 0;
}