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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#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;
}