01 分数编程 - 丁克巴赫算法

首先关于01分数规划的定义与二分法，请参考我的另一个博客

 正文

这个算法说难，理解难，说简单，方法简单。

这个算法核心思想是用一个解去推出更优的解，用迭代来实现。

1. 我们对于一个解 r ，可以求出这个解对应的最优的所有 x_{i 。}

2. 用这个 x_i 来求出所有 x_i 对应的最优解。

3. 判断是否为全局最优解（如果这个解是最优，那么他与上一个求出来的解相等），是则退出循环，否则回到1。

 

下面我们用一个样例说明一下：

原题：poj2976

我们要从下面4组数中取出3组数，使取出的 r=(∑a_i)/(∑b_i) 最大

a：3, 2, 4, 1

b：5, 3, 4, 2

先随意取 r=0.5 。

得 c：0.5, 0.5, 2, 0 （ c_i=a_i-b_ir ，至于原因看开头提到的那个博客）

排序得 c：2[3], 0.5[1], 0.5[2], 0[4] （方括号内的是在没排序前的下标，也就是各自的 i ）

我们取 c 的前3个的 p=∑a_i=9, q=∑b_i=12 _。

那么就得到新的解 r'=9/12=0.75 。

因为和上一个不相等，所以继续。

r=r'=0.75

c：-0.75, -0.25, 1, -0.5

c：1[3], -0.25[2], -0.5[4], -0.75[1]

p=7, q=9, r'=0.77...78

不等于，再重复一次。

r=r'=0.77...78

c：-0.88...89, -0.33...3, 0.88...89, -0.55...56

c：0.88...89[3], -0.33...33[2], -0.55...56[4], -0.88...89[1]

p=7, q=9, r'=0.77...78

现在我们发现等于了！那么终止循环，而0.77...78就是最后的结果。

参考博客

https://blog.****.net/longshuai0821/article/details/7872039

https://blog.****.net/lvzelong2014/article/details/79125142

 

ps：如果你是从洛谷来的，那么恭喜你发现彩蛋~