M_sea

0/1分数规划学习笔记
这是一篇咕了的总结概念0/1分数规划用来求一个分式的极值。形象一点就是,给出$a[i]$和$b[i]$,求一组$w...
扫描右侧二维码阅读全文
22
2019/01

0/1分数规划学习笔记

这是一篇咕了的总结

概念

0/1分数规划用来求一个分式的极值。

形象一点就是,给出$a[i]$和$b[i]$,求一组$w[i]\in\{0,1\}$,使得$\large \frac{\;\sum\limits_{i=1}^na[i]\cdot w[i]\;}{\;\sum\limits_{i=1}^nb[i]\cdot w[i]\;}$最大/最小。

算法

最基本的方法:二分

假设我们要求最大值。二分一个答案$mid$,然后推式子(少写了上下界):

$\large \frac{\sum a[i]\cdot w[i]}{\sum b[i]\cdot w[i]}>mid\Rightarrow\\\large\sum a[i]\cdot w[i]-mid\cdot \sum b[i]\cdot w[i]>0\Rightarrow\\\large\sum w[i]\cdot(a[i]-mid\cdot b[i])>0$

这是一般形式,我们只要求出左边这个东西最大值就行了。

如果最大值比$0$要大,说明$mid$是可行的,否则不可行。

实例

下面结合一系列题目来理解左边这个东西的最大值的求法。

POJ2976 Dropping tests

没有任何的限制,考虑怎么求。

把$a[i]-mid\cdot b[i]$作为每个物品的权值,然后大于$0$的就选,这样子就能得到最大值。

洛谷4377 Talent Show

多了一个总重量至少为$W$的限制。

考虑DP。把$b[i]$作为体积,$a[i]-mid\cdot b[i]$作为价值,然后就是一个背包了。

POJ2728 Desert King

这个东西叫做最优比率生成树。

将$a[i]-mid\cdot b[i]$作为每条边的权值,然后跑最小生成树即可。

这道题是稠密图,所以要用$\texttt{Prim}$,不然会炸?

洛谷3199 [HNOI2009]最小圈

这个东西叫最优比率环。

沿用上面的做法,将$a[i]-mid\cdot b[i]$作为边权,然后检查有没有负环即可。

洛谷3705 [SDOI2017]新生舞会

将$a_{i,j}-mid\cdot b_{i,j}$作为$(i,j)$边的边权。

然后跑费用流,最大费用就是最大值。

UVA1389 Hard Life

这个东西叫做最大密度子图。

我现在还不会,以后再补。咕咕咕

总结

怎么说呢...感觉0/1分数规划都是套路,重点还是在于求解$\sum w[i]\cdot (a[i]-mid\cdot b[i])的最大值$。

参考资料

最后修改:2019 年 06 月 25 日 08 : 32 PM

发表评论