分数规划/01规划

分数规划/01规划

今天也是Mivik被智商碾压的一天啊QwQ

分数规划 貌似 和01规划是一个东西吧QwQ

问题

我们现在要求这样一个式子的最大值

$$
\frac{\sum e_i.a}{\sum e_i.b}
$$

其中 $e$ 中的元素是可以选择的,且 $e_i.a > 0$ ,$ e_i.b > 0$

:这不是简单题吗?


垃圾Mivik的思路

首先对于每个矢量 $e_i$ ,求出它的性价比,即 $\frac{e_i.a}{e_i.b}$,然后在题目要求的范围内每次选出性价比最高的一个加入到集合 $e$ 中

但是这样会被卡QwQ

Hack

要求在下面三个元素中选两个使得 $\frac{\sum e_i.a}{\sum e_i.b}$ 最大:

ID a b 性价比
1 2 1 2
2 3 1 3
3 2 0.1 20

显然2和3的性价比是最高的,我们按照贪心策略选出他们,最后的到的答案是

$$
\frac{1+3}{2+0.1}\approx1.90476
$$

但显然选1和2得出的答案更优

$$
\frac{2+3}{1+1}=2.5
$$

所以在有分数的情况下贪心是行不通的,因为:

$$
\sum \frac{e.a}{e.b}\not=\frac{\sum e.a}{\sum e.b}
$$

Mivik因此放弃了尝试~~

解题思路

我们设这个式子的最大值为ans,即

$$
Max(\frac{\sum e_i.a}{\sum e_i.b})=ans
$$

那么假设我们现在已经找到一种 $e$ 的组成方案,那么必有

$$
\frac{\sum e_i.a}{\sum e_i.b}\le ans \tag{1}
$$

移项,可得

$$
\sum e_i.a-\sum (ans \cdot e_i.b) \le 0 \tag{2}
$$

那么事情就变得很清晰了

我们只需要二分 $ans$ ,然后将 $e_i.a-(ans\cdot e_i.b)$ 作为 $e$ 的性价比,然后就可以用贪心做了

具体一点,如果我们当前枚举到的这个 $ans$ 使得用贪心(每次都选择性价比最小的 $e$ )得出的 $e$ 集合满足 $(2)$ 式,也就是说满足 $(1)$ 式,那么说明我们的 $ans$ 是大于等于正确的 $ans$ ,那么我们就执行 $R=mid$ ,往下去二分正确的 $ans$ ,否则就 $L=mid$

为什么是 $L=mid$ 和 $R=mid$ 而不是 $L=mid+1$ 和 $R=mid-1$ 呢?

因为 $ans$ 是个小数,我们在对小数进行动态规划时不能加1啊QwQ


例题

P2868 - Sightseeing Cows 观光的奶牛

题意即给出一个有向图(没有重边),求出此无向图的一个环使得

$$
\frac{\sum V_i.f}{\sum E_i.d}
$$

最大,其中 $V$ , $E$ 分别为环的点集和边集,且 $V_i.f$ 和 $E_i.d$ 都已经给出。

解题思路

我们按照上面的01规划对题中的式子变化一下

$$
\sum V_i.f-\sum (ans \cdot E_i.d) \le 0 \tag{3}
$$

但是!题目中要求我们求出来的必须是一个环,这就限定了 $V$ 和 $E$ 必须构成一个环,这该怎么办呢?

我们来观察一个环

一个可怜的环

我们不难发现

分割

这个节点数为4的环可以被分成4个部分

其中,每一个部分都包含了一个点和从这个点出去的一条边

因此我们考虑在原图上跑最短路,每走一条边 $e$ 就把 $dis[e.to]$ 更新为

$$
min{dis[e.to],dis[e.from]+e.from.f-ans\cdot e.d}
$$

那么我们如果最后检测出了负环,那说明这个环上的 $V$ 和 $E$ 是满足式 $(3)$ 的,那么我们按照上面给出的思路二分就好了

代码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>

#define endl '\n'
#define USING_R(fn,n) n fn() {static n _R;static char _C;static bool _F;_F=0;_R=0;_C=GG();while((_C<'0'||_C>'9')&&_C!='-'&&_C!='\0')_C=GG();if(_C=='-')_F=1,_C=GG();while(_C>='0'&&_C<='9')_R=(_R<<3)+(_R<<1)+_C-'0',_C=GG();if (_F) _R=-_R;return _R;}
#define R Read()
#define GG getchar

#define nmax 1005
#define mmax 5005
#define eps 1e-4
using namespace std;

USING_R(Read,int)
int n,m;
int re[nmax];
int lst[nmax];
int pre[mmax],tar[mmax],wei[mmax];
bool vi[nmax],fu[nmax];
double dis[nmax];
double T;
bool dfs(int x) {
vi[x]=1;
fu[x]=1;
double w;
for (int b=lst[x],v;b;b=pre[b]) {
v=tar[b];
w=dis[x]+wei[b]*T-re[v];
if (w<dis[v]) {
dis[v]=w;
if (vi[v]) return 1;
if (dfs(v)) return 1;
}
}
vi[x]=0;
return 0;
}
bool check() {
for (int i=1;i<=n;i++) vi[i]=dis[i]=fu[i]=0;
for (int i=1;i<=n;i++) if (!fu[i]) if (dfs(i)) return 1;
return 0;
}
int main() {
n=R,m=R;
register int i,j;
double l=0,r=0;
for (i=1;i<=n;i++) r+=re[i]=R;
for (i=1;i<=m;i++) {
j=R;
pre[i]=lst[j],lst[j]=i;
tar[i]=R,wei[i]=R;
}

while (r-l>eps) {
T=(l+r)/2;
if (check()) l=T;
else r=T;
}
printf("%.2f",l);
return 0;
}

更多例题

P3288 [SCOI2014]方伯伯运椰子


(终于写完,Mivik快废了)

(纯手绘,图丑勿喷)

作者

Mivik

发布于

2019-09-20

更新于

2021-05-31

许可协议

评论