题目描述
Farmer John要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第iii头奶牛重量为wi，才艺水平为ti，两者都是整数。 在到达时，Farmer John就被今年达牛秀的新规则吓到了：
（一）参加比赛的一组奶牛必须总重量至少为W（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且
（二）总才艺值与总重量的比值最大的一组获得胜利。
FJ注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。
题解
经典的0/1分数规划模型。
最大化ans=Σai*ti/Σai*wi （其中ai是0/1表示选不选）
套路的二分加判断。
简单推一下。
二分判断的本质是要找，是否存在和mid有关的一组解，从而来更新二分的范围。
假设mid<=ans的话，
那么，mid<=Σai*ti/Σai*wi
Σai*ti-Σai*wi*mid>=0
Σai*(ti-wi*mid)>=0
那么，判断就转化为了，是否存在一组ai，
满足ai*wi>=W,并且Σai*(ti-wi*mid)>=0
那么只要最大化这个式子，看是否大于等于0
0/1分数规划ai就是一个选择或者不选的问题。
每个牛有一个价值ti-wi*mid，重量wi，
所以0/1背包即可。
wi太大？
W很小，>W的话，直接放入W+1即可。
如果f[W],f[W+1]>=0的话，返回true反之false
注意0/1背包循环顺序（天啊）
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=255;
const int M=1005;
const double inf=19260817487525.00;
const int eps=0.0001;
int n,w0;
double ans;
double l,r;
double f[M];
int w[N],t[N];
double v[N];
bool che(double mid){
for(int i=1;i<=n;i++){
v[i]=(double)t[i]-(double)w[i]*mid;
}
for(int i=1;i<=w0+1;i++)f[i]=-inf;f[0]=0.00;
for(int i=1;i<=n;i++){
for(int j=w0+1;j>=0;j--){
f[min(j+w[i],w0+1)]=max(f[min(j+w[i],w0+1)],f[j]+v[i]);
}
}
return (f[w0]>=eps||f[w0+1]>=eps);
}
int main()
{
scanf("%d%d",&n,&w0);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&t[i]);
r+=(double)t[i];
}
l=0.00;
while(r-l>0.0001){
double mid=(l+r)/2.0;
bool fl=che(mid);
if(fl) ans=mid,l=mid;
else r=mid;
}
//cout<<ans<<endl;
int op=ans*1000;
printf("%d",op);
return 0;
}
总结：
1.0/1分数规划问题，关键点在于对二分的判断的模型构建。
必须要推判定mid<=ans（这个是最大化ans的情况）的条件（注意是判断存在性），配合每个物品选择或者不选择，构建模型。
2.对于>W的就认为是W+1的条件，是因为这只是要判定，>W都符合了，我们不关心到底是多少。
值得注意。