题解 P4377 【[USACO18OPEN]Talent Show】
这道题所需要的知识点是：01分数规划 背包dp
首先01分数规划更像是一种数据的转化，相信不少童鞋都试着贪心来着，然额几经波折的你最后也许会发现贪心是彻底错误的，归结到底还是因为这个式子有个“/”号╰（‵□′）╯
而01分数规划就是将这样的数据处理需求“可贪心化”，下面看看她是怎么做到的
首先定义一个数组x，x[i]表示的是这一头牛拿不拿，如果拿赋值成1，不拿就是0
那么则有答案R=sigma(t[i]*x[i])/sigma(w[i]*x[i])我们需要R最大，现在我们假设有一个没那么优的答案Z满足Z<=R，那么就会有如下的式子： sigma(t[i]*x[i])>=sigma(w[i]*x[i])*Z
也就是sigma((t[i]-w[i])*x[i]*Z)>=0
我天！每头牛的贡献竟然变成了(t[i]-w[i])*x[i]*Z，与其他牛无关了有木有！这下不久可以贪心了吗！只要在最优选取的状态下可以使总和非负，就说明这个Z是可行的，答案还可以进一步变大！
所以，与二分配合，进行01分数规划就是这题的第一步。
然而在验证的时候也有些小问题，这里要求奶牛们的总质量必须不小于W，这就很难愉快的贪心了啊。。。不过我们还有应对办法，用背包啊！
设f[i]为当前选择的奶牛总质量为i时sigma((t[i]-w[i])*x[i]*Z)最大是多少，因为这有可能是负数，所以初值最好弄成负无穷
接下来以零一背包的模式dp就好了，不过要注意，要把所有总质量大于等于W的更新全算在f[W]上。这里如果有点蒙可以详见代码
总之希望这篇题解对你有帮助！d=====(￣▽￣*)b
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,W;
int w[300],t[300];
long long f[10000];
bool check(int z){
memset(f,128,sizeof(f));f[0]=0;
long long tmp=f[W];
for(int i=1;i<=n;i++){
for(int j=W;j>=0;j--)if(f[j]!=tmp){
int jj=j+w[i];jj=min(jj,W);
f[jj]=max(f[jj],f[j]+t[i]-(long long)w[i]*z);
}
}
return f[W]>=0;
}
int erfen(){
int l=0,r=1000000;
while(l<=r){
int mid=l+r>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
return l-1;
}
int main(){
scanf("%d%d",&n,&W);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&t[i]);
t[i]*=1000;
}
printf("%d",erfen());
return 0;
}