01 分数规划
什么是 01 分数规划
用人话说，就是：
有 \(n\) 个玩意儿，每个都有两个属性 \((x,y)\)。现在要从中选出几个玩意儿，使得 \(\frac{\sum x}{\sum y}\) 最大
但是有些人仍然不懂。没关系，可以用数学语言表示：
有三个序列 \(x,y,z\) 长度为 \(n\)。
\(z\) 满足 \(\forall i\in [1,n],z_i\in(1,0)\)
然后得到一种合法的 \(z\) 的取值，最大化：
\[\frac{\sum\limits_{i=1}^{n} x_i\times z_i}{\sum\limits_{i=1}^{n} y_i\times z_i} \]
怎么解这个问题
解法：二分法。
首先先转移：
令 \(L=\frac{\sum\limits_{i=1}^{n} x_i\times z_i}{\sum\limits_{i=1}^{n} y_i\times z_i}\)， 则
\[L\times \sum\limits_{i=1}^{n} y_i\times z_i=\sum\limits_{i=1}^{n} x_i\times z_i \\
\Downarrow\\
\sum\limits_{i=1}^{n} x_i\times z_i-L\times \sum\limits_{i=1}^{n} y_i\times z_i=0 \\
\Downarrow\\
\sum\limits_{i=1}^{n} (x_i-y_i\times L)\times z_i=0
\]
相当于拥有了一个数组 \(a,a_i=x_i-y_i\times L\)，从\(a\)中选一些数使得总和最大。
显然，选择所有的正数即可。
这个 \(L\) 就是二分中的 \(mid\) 了。
由于这个 \(L\) 是二分得到的，所以每一次不一定都是
\[\sum\limits_{i=1}^{n} (x_i-y_i\times L)\times z_i=0
\]
而是
\[\sum\limits_{i=1}^{n} (x_i-y_i\times L)\times z_i\geq0
\]
也就是在代码的二分中判断此刻的 \(mid\) 可不可行时，在 if 里面写上这个。
板题
这个不算很板的题目，贴一下吧。
P4377 [USACO18OPEN] Talent Show G
这里附一份代码：
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+5;
const double eps=1e-6;
int n,W;
int w[MAXN],t[MAXN],maxz;
double a[MAXN];
double f[MAXN];
signed main()
{
scanf("%lld%lld",&n,&W);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&w[i],&t[i]),maxz+=t[i];
double l=0,r=maxz;
while(r-l>eps)
{
double mid=(l+r)/2;
for(int i=1;i<=n;i++)
a[i]=t[i]-w[i]*mid;
for(int i=1;i<=W;i++) f[i]=-1e9;
for(int i=0;i<=n;i++)
{
for(int j=W;j>=0;j--)
f[min(j+w[i],W)]=max(f[min(j+w[i],W)],f[j]+a[i]);
}
if(f[W]>=eps)
l=mid;
else
r=mid-eps;
}
printf("%lld\n",(int)floor(1000*l));
return 0;
}