0/1分数规划
二分与0/1分数规划
0/1分数规划问题：
给定两个都包含 n 个数的正整数序列 {a_1,a_2,...,a_n} 和
{b_1,b_2,...,b_n} ，同时选出 k 个 a 和 b ，求 \max\frac{\sum_{i=1}^{n}a_is_i }{\sum_{i=1}^{n}b_is_i} ，其中 \huge{s_i\in [0,1]} ，表示选不选 a_i 和 b_i ，且 \huge{\sum_{i=1}^{n}s_i=k} 。
如果使用暴力枚举，对 n 个数进行排列组合，时间复杂度为 O(2^n) ，显然不行。为什么是 O(2^n) ？因为每个数有两种可能，共 n 个数，所以为 O(n) 。
这样的复杂度显然是不可取的！为了加快速度，可以用猜数的方法，猜测一个数 x （很像在 100 内猜一个数），使
移项得： \huge{f=\sum_{i=1}^{n}(a_i-xb_i)s_i\ge x} 。
令 y=a_i-xb_i ，把 x 和 y 看作变量，这是一条直线。原问题转化为在 n 条直线中选 k 条直线求和。这 n 条直线如图1所示。
一条直线 y_i 与 x 轴的交点（横截距）等于单独选这条直线的最大值 {\large \frac{a_i}{b_i}} 。
用直线理解0/1分数规划问题，非常直观易懂。选 k 对数的 f 值等于选 k 条直线所组合的 y 值之和，当 f=0 ，是 f 与 x 轴的交点。选不同的 k 条直线会有不同的结果，最大时 x=M 。
- k=1 ，选一对数，求出 \huge{\max\frac{a_i}{b_i},i\in[1,n]} 即可。
- k=2 ，选两对数，在所有使 y_i+y_j=0 的 x 中，最大的就是答案 $M$。如果用暴力确定 M ，有 C_n^2 中可能。
看到这里，我们可以发现，暴力枚举是不可取的，复杂度增长很快。这时要使用二分法。
二分的初始区间为 [L,R] ， L=0,R 是大于答案的值，如设为 \sum_{i=1}^{n}a_i 。
步骤：
从 x=R 开始，计算所有的 y_i=a_i-xb_i ，排序，求 f=\sum_{i=1}^{k}y_i ，若 f<0 ，说明 x 小了；反之大了。
洛谷P10505 Dropping Test是一道模板题。代码中做了 50 次二分，执行一次 check() 函数复杂度为 O(nlog_2n) 。
Dropping Test
题目描述
在某个课程中，你需要进行 n 次测试。
如果你在共计 b_i 道题的测试 i 上的答对题目数量为 a_i ，你的累积平均成绩就被定义为
100\times \dfrac{\displaystyle \sum_{i=1}^n a_i}{\displaystyle \sum_{i=1}^n b_i}给定您的考试成绩和一个正整数 k ，如果您被允许放弃任何 k 门考试成绩，您的累积平均成绩的可能最大值是多少。
假设您进行了 3 次测试，成绩分别为 5/5,0/1 和 2/6 。
在不放弃任何测试成绩的情况下，您的累积平均成绩是
100\times \frac{5+0+2}{5+1+6}=50然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了
100\times \frac{5+0}{5+1}\approx 83.33\approx 83输入格式
输入包含多组测试用例，每个测试用例包含三行。
对于每组测试用例，第一行包含两个整数 n 和 k 。
第二行包含 n 个整数，表示所有的 a_i 。
第三行包含 n 个整数，表示所有的 b_i 。
当输入用例 n=k=0 时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一行结果，表示在放弃 k 门成绩的情况下，可能的累积平均成绩最大值。
结果应四舍五入到最接近的整数。
样例 #1
样例输入 #1
3 1 5 0 2 5 1 6 4 2 1 2 7 9 5 6 7 9 0 0样例输出 #1
83 100提示
数据范围 1 \le n \le 1000, 0 \le k < n, 0 \le a_i \le b_i \le 10^9 。
代码如下：
bool check(double x){
for(int i=0;i<n;i++){
p[i].y=p[i].a*1.0-x*p[i].b;
}
sort(p,p+n);
double f=0;
for(int i=0;i<k;i++){
f+=p[i].y;
}
return f<0;
}
while(scanf("%d%d",&n,&k)==2&&n+k){
k=n-k;
for(int i=0;i<n;i++){
scanf("%d",&p[i].a);
}
for(int i=0;i<n;i++){
scanf("%d",&p[i].b);
}
double l=0,r=0;
for(int i=0;i<n;i++){
r+=p[i].a;
}
for(int i=0;i<50;i++){
double mid=l+(r-l)/2;
if(check(mid)){
r=mid;//线在M右侧，左移。
}else{
l=mid;//线在M左侧，右移。
}
}
printf("%d\n",(int)(100*(l+0.005)));//四舍五入。
}
0/1分数规划的应用
0/1分数规划是一种简单的数学模型，常与一些特定的场景结合出题，如：
- 最优比率背包，与0/1背包结合。
- 最优比率生成树，与生成树结合。
洛谷P4377 [USACO18OPEN] Talent Show G就是一道最优比率背包的题目。
本题用0/1背包建模：有 n 个物品，物品 i 的重量为 w_i ，价值为 t_i ，选出一些物品，要求总重量大于等于 W ，求最大价值。
本题和基本的0/1分数规划很像，目标 \huge{\frac{\sum_{i=1}^{n}t_is_i}{\sum_{i=1}^{n}w_is_i}(s_i\in[0,1])} ，只是结束条件为 \huge{\sum_{i=1}^{n}w_is_i\ge W} 。
代码很简单：
int n,W;
struct Cow{
int w,t;
double y;
}a[maxn];
double f[maxm];
bool check(double x){
for(int i=1;i<=n;i++){
a[i].y=(double)a[i].t-x*a[i].w;
}
//0/1背包模板。
for(int i=1;i<=W;i++){
f[i]=-inf;
}
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=W;j>=0;j--){
if(j+a[i].w>=W){
f[W]=max(f[W],f[j]+a[i].y);
}else{
f[j+a[i].w]=max(f[j+a[i].w],f[j]+a[i].y);
}
}
}
return f[W]<0;
}
【习题】
Let`s have a test! 
