制作网站的软件/娄底seo
01分数规划算法 信息学竞赛 OI ACM 二分 Dinkelbach 最优比率生成树 最优比率环
01分数规划
张天翔
blog.csdn.net/hzoi_ztx
ztx97@qq.com
前置技能
- 二分思想
- 最短路算法
- 一些数学脑细胞？
问题模型1
基本01分数规划问题
给定nnn个二元组(valuei,costi)(value_i,cost_i)(valuei,costi)，valueivalue_ivaluei是选择此二元组获得的价值（非负），costicost_icosti是选择此二元组付出的代价（非负），设xi(xi∈{0,1})x_i(x_i\in \{0,1\})xi(xi∈{0,1})代表第iii个二元组的选与不选，最大(小)化下式
maximize(orminimize)r=∑valuei⋅xi∑costi⋅ximaximize(or\ minimize)\ \ \ r = \frac{\sum value_i \cdot x_i}{\sum cost_i\cdot x_i} maximize(or minimize) r=∑costi⋅xi∑valuei⋅xi
下面先说最大化
解决方法
二分法
设rrr最大值为r∗r^*r∗，
r∗=∑valuei⋅xi∑costi⋅xir^* = \frac{\sum value_i \cdot x_i}{\sum cost_i\cdot x_i} r∗=∑costi⋅xi∑valuei⋅xi
∑valuei⋅xi−r∗⋅∑costi⋅xi=0\sum value_i \cdot x_i - r^*\cdot \sum cost_i\cdot x_i = 0 ∑valuei⋅xi−r∗⋅∑costi⋅xi=0
设一个函数，自变量为rrr值，
f(r)=∑valuei⋅xi−r∗⋅∑costi⋅xif(r) =\sum value_i \cdot x_i - r^*\cdot \sum cost_i\cdot x_i f(r)=∑valuei⋅xi−r∗⋅∑costi⋅xi
观察这个函数，假如{xi}\{x_i\}{xi}固定，则这个函数就是坐标系中一条直线(y=B−A⋅xy = B - A\cdot xy=B−A⋅x)，每一组{xi}\{x_i\}{xi}对应着一条直线，这些直线斜率非正(因为−A=−∑costi⋅xi≤0-A =- \sum cost_i\cdot x_i \le 0−A=−∑costi⋅xi≤0)，纵截距非负(因为B=∑valuei⋅xi≥0B =\sum value_i \cdot x_i \ge 0B=∑valuei⋅xi≥0 )，如图1。
对于每一条直线，当f(r)=0f(r)=0f(r)=0时，横截距就是这一组的rrr，那么r∗r^*r∗就是每条直线横截距的最大值（每组{xi}\{x_i\}{xi}对应rrr的最大值）如图2。
在图中上任取一条垂直xxx轴的竖线，
如果存在直线与这条竖线的交点纵坐标为正，那么最优值一定在当前竖线的右侧；
如果所有直线与这条竖线交点纵坐标为负，那么最优值一定在当前竖线的左侧；
如果所有直线与这条竖线交点纵坐标非正且存在直线与这条竖线交点纵坐标为0，那么当前竖线横坐标即为最优值r∗r^*r∗。
按照这个思想，可以二分答案rrr，那么二分时如何进行判断呢？
选择一个rrr时需要判断所有f(r)f(r)f(r)的最大值是否为0，如果max{f(r)}>0max\{f(r)\} > 0max{f(r)}>0则r<r∗r < r^*r<r∗；如果max{f(r)}<0max\{f(r)\} < 0max{f(r)}<0 则 r>r∗r > r*r>r∗。
怎样求max{f(r)}max\{f(r)\}max{f(r)}?
f(r)=∑valuei⋅xi−r⋅∑costi⋅xi=∑(valuei−r⋅costi)⋅xi\begin{aligned} f(r) &= \sum value_i \cdot x_i - r \cdot \sum cost_i\cdot x_i \\ &= \sum (value_i-r\cdot cost_i) \cdot x_i \end{aligned} f(r)=∑valuei⋅xi−r⋅∑costi⋅xi=∑(valuei−r⋅costi)⋅xi
二分一个rrr时，每个二元组的valuei−r⋅costivalue_i-r\cdot cost_ivaluei−r⋅costi 都可以求出，设其为weightiweight_iweighti，现在的目标就是找到一组{xi}\{x_i\}{xi}使得∑wighti⋅xi\sum wight_i\cdot x_i∑wighti⋅xi最大（即求max{f(r)}max\{f(r)\}max{f(r)}）。怎么找到这一组{xi}\{x_i\}{xi}，或者直接求得max{f(r)}max\{f(r)\}max{f(r)}呢？具体问题具体分析，经常借助最短路算法判断是否存在负环。下面会有几道例题。
01分数规划还会与其他问题结合，如网络流等。
DinkelbachDinkelbachDinkelbach算法
这个算法我是在写这篇文章时才知道的。
思考上述二分算法的思路，设二分过程中某一个二分值为rrr，二分时的判断条件是max{f(r)}max\{f(r)\}max{f(r)}的正负性，而这个rrr除了让LLL右移或者RRR左移就没有用了。现在思考某一过程中rrr与max{f(r)}max\{f(r)\}max{f(r)}能否再被利用。
二分时，假如max{f(r)}>0max\{f(r)\}>0max{f(r)}>0这说明最优解在当前rrr的右侧，于是让L=rL=rL=r，但是，如果将LLL移动到max{f(r)}max\{f(r)\}max{f(r)}对应直线的横截距呢？显然，算法会变得更快。这个思想就是DinkelbachDinkelbachDinkelbach算法的内涵。
DinkelbachDinkelbachDinkelbach实质上是一种迭代算法，基于这样的思想：不去二分答案，而是先随便给定一个答案，然后根据更优的解（max{f(r)}max\{f(r)\}max{f(r)}对应直线的横截距）不断移动答案，逼近最优解。理论上它比二分快些。
在这个算法中，一般将rrr初始化为000。
再说最小化
看上面的图，也很好理解，就是最左边的rrr为r∗r^*r∗，当前的rrr确定时需要用到min{f(r)}min\{f(r)\}min{f(r)}。
如果min{f(r)}>0min\{f(r)\}>0min{f(r)}>0，那么r<r∗r < r^*r<r∗；
如果min{f(r)}=0min\{f(r)\}=0min{f(r)}=0，那么r=r∗r = r^*r=r∗；
如果min{f(r)}<0min\{f(r)\}<0min{f(r)}<0，那么r>r∗r > r^*r>r∗。
做题时认清哪个是valueivalue_ivaluei，哪个是costicost_icosti，再记住上面几张图，基本不会出错了。
两种算法的比较
DinkelbachDinkelbachDinkelbach算法的弊端就是需要保存解。这两个算法解决统一问题实际上都有可能快些。
我觉着我一般还是用二分。。。。
例题
[POJ2976]Dropping tests
问题模型2
最优比率生成树
带权无向图GGG， 对于图中每条边eie_iei， 都有valueivalue_ivaluei和costicost_icosti，现在求一棵生成树TTT，最大（小）化∑valuei∑costi,ei∈T\frac{\sum value_i}{\sum cost_i},e_i\in T∑costi∑valuei,ei∈T
解决方法
套用01分数规划模型，如果ei∈Te_i\in Tei∈T则xi=1x_i=1xi=1否则xi=0x_i=0xi=0。
二分法
二分答案rrr，边赋值weighti=valuei−r⋅costiweight_i = value_i-r\cdot cost_iweighti=valuei−r⋅costi，因为是生成树，边的数量确定，那么max{f(r)}max\{f(r)\}max{f(r)}需要选取前∣G∣−1|G|-1∣G∣−1大的weightiweight_iweighti，也就是求最大生成树，按最大生成树权值的正负性就可以二分了。最小化就求最小生成树。
DinkelbachDinkelbachDinkelbach算法
当前答案rrr，边赋值weighti=valuei−r⋅costiweight_i = value_i-r\cdot cost_iweighti=valuei−r⋅costi，同样求最大生成树，找到max{f(r)}max \{f(r)\}max{f(r)}对应的边集{xi}\{x_i\}{xi}，也就是最大生成树的边集。对这个边集找横截距当做下一次答案。横截距是啥呢？
f(r)=B−A⋅r=0r=B/Ar=∑valuei⋅xi∑costi⋅xi\begin{aligned} f(r)=B-A\cdot r &= 0 \\ r&=B/A \\ r &=\frac{\sum value_i \cdot x_i}{ \sum cost_i\cdot x_i} \end{aligned} f(r)=B−A⋅rrr=0=B/A=∑costi⋅xi∑valuei⋅xi
最小化就求最小生成树。
例题
[POJ2728]Desert King
问题模型3
最优比率环
给定有点权和边权的图，求一个环，使得环的点权和与边权和的比值最大。
解决方法
套用01分数规划模型，点权为valueivalue_ivaluei，边权为costicost_icosti，一个环为CCC
问题要求最大化∑valuei∑costi,(i∈C)\frac{\sum value_i }{\sum cost_i},(i\in C)∑costi∑valuei,(i∈C)
边数和点数是相同的，但上述式子表述不是很正确，意会即可。
若答案为r∗r^*r∗，那么任意一个环
∑valuei∑costi≤r∗∑valuei≤r∗⋅∑costir∗⋅∑costi−∑valuei≥0\begin{aligned} \frac{\sum value_i }{\sum cost_i}&\le r^* \\ \sum value_i&\le r^*\cdot \sum cost_i \\ r^*\cdot \sum cost_i -\sum value_i &\ge 0 \end{aligned} ∑costi∑valuei∑valueir∗⋅∑costi−∑valuei≤r∗≤r∗⋅∑costi≥0
最小化时
∑valuei∑costi≥r∗∑valuei≥r∗⋅∑costi∑valuei−r∗⋅∑costi≥0\begin{aligned} \frac{\sum value_i }{\sum cost_i}&\ge r^* \\ \sum value_i&\ge r^*\cdot \sum cost_i \\ \sum value_i - r^*\cdot \sum cost_i &\ge 0 \end{aligned} ∑costi∑valuei∑valuei∑valuei−r∗⋅∑costi≥r∗≥r∗⋅∑costi≥0
二分法
设当前答案rrr，
r<r∗r < r^*r<r∗，至少存在一个环，r⋅∑costi−∑valuei<0r \cdot \sum cost_i -\sum value_i < 0r⋅∑costi−∑valuei<0，即存在负权回路（将边权设为r⋅costi−valueir\cdot cost_i-value_ir⋅costi−valuei，不是提前算出，而是在更新路径的时候从哪个点访问到这条边的就将这条边设为相应点权与边权的对应值）；
r≥r∗r\ge r^*r≥r∗，则不存在负环。
求负环可以用Bellman-Ford，但是比较慢，一般用spfa算法求负环
具体判断方法为，一个点不能入队nnn次，否则有负环；一条最短路径长度不能到nnn，否则有负环。两个判断方法可以同时使用。
最小化时边权设为 ∑valuei−r⋅∑costi\sum value_i -r \cdot \sum cost_i∑valuei−r⋅∑costi即可，同样也是更新时算出此值。
以上具体实现看例题。
DinkelbachDinkelbachDinkelbach算法
如果用这个算法需要记录下来一个负环，实现还是能实现的，但是没有二分+spfa好写。
例题
[POJ3621]Sightseeing Cows
问题模型4
最大密度子图
这个问题会写在网络流总结中。
更多
更多题目在01分数规划中。
参考资料
【1】KirisameMarisa - NYIST 914Yougth的最大化【二分搜索/Dinkelbach算法】
【2】PerSeAwe - ［Algorithm］01分数规划