LG4377 「USACO2018OPEN」Talent Show 分数规划+背包

问题描述

LG4377

题解

有 \(n\) 个物品，每个物品有两个权值 \(a,b\)

需要确定一组 \(w_i \in [0,1]\) ，使得 \(\frac{\sum{w_i \times a_i}}{\sum{w_i \times b_i}}\) 最大。

要求 \(\sum{w_i \times b_i \ge W}\) 。

分数规划，二分答案的 \(\mathrm{check}\) 函数采用背包进行判断。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=1007;

int n,w;
int a[maxn];
int b[maxn];
long long f[maxn];
bool check(int mid){
    memset(f,0xcf,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=w;j>=0;j--){
            if(f[j]==f[w+1]) continue;
            int pos=min(w,j+a[i]);
            f[pos]=max(f[pos],f[j]+b[i]-(long long)a[i]*mid);
        }
    }
    return f[w]>=0;
}

int main(){
    read(n);read(w);
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i],b[i]*=1000;
    int L=0,R=1000000;
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid)) L=mid+1;
        else R=mid-1;
    }
    printf("%d\n",L-1);
    return 0;
}