0/1 分数规划与 Dinkelbach 迭代法

2018-07-10

0/1 分数规划是一种常见的模型:给你 n 个价值 a_i 与 n 个代价 b_i,让你选出 m 个数字,使得 \sum \frac {a_i} {b_i} 最大。显然这种题目可以用二分,但是有一种更优秀的方法:Dinkelbach 迭代法。

Read more...