01分数规划——Dinkelbach算法⾸先关于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 i r ，⾄于原因看开头提到的那个博客）
排序得 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：-89, -3, 89, -0.55 (56)
c：89[3], -33[2], -56[4], -89[1]
p=7, q=9, r'=0.77 (78)
高压电线杆
现在我们发现等于了！那么终⽌循环，⽽78就是最后的结果。压铸机料筒的设计
参考博客
ps：如果你是从洛⾕来的，那么恭喜你发现彩蛋~
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议