首页 > 其他 > 详细

【数论】0 / 1 分数规划

时间:2020-09-19 13:14:06      阅读:44      评论:0      收藏:0      [点我收藏+]

我们要解决的是 \(\dfrac{\sum\limits_{i=1}^n a_i \times x_i}{\sum\limits_{i=1}^n b_i \times x_i}\),其中 \(x_i \in \{0, 1\}\),要求让上述式子最大值。

我们考虑转换问题,若 \(\exists \ L\),满足 \(\sum\limits_{i=1}^n x_i \times(a_i - b_i \times L) \geq 0\),那么 \(\sum\limits_{i=1}^n x_i \times a_i \geq \sum\limits_{i=1}^n x_i \times b_i \times L\),此时,\(\dfrac{\sum\limits_{i=1}^n a_i \times x_i}{\sum\limits_{i=1}^n b_i \times x_i}\) 的最大值一定 \(\geq L\),若 \(\nexists \ L\),满足 \(\sum\limits_{i=1}^n x_i \times(a_i - b_i \times L) \geq 0\),那么 \(\sum\limits_{i=1}^n x_i \times a_i < \sum\limits_{i=1}^n x_i \times b_i \times L\),此时,\(\dfrac{\sum\limits_{i=1}^n a_i \times x_i}{\sum\limits_{i=1}^n b_i \times x_i}\) 的最大值一定 \(< L\),我们发现这个 \(L\) 是满足单调性的,于是我们可以二分这个 \(L\)

现在问题就变为了如何判定是否存在 \(x_i\) 满足 \(\sum\limits_{i=1}^n x_i \times(a_i - b_i \times L) \geq 0\),这个很简单,当 \(a_i - b_i \times L > 0\) 时,我们便让 \(x_i = 1\),否则 \(x_i = 0\)

于是这个问题就在 \(O(n \log \max\{L\})\) 解决了。

若限制 \(x_i\)\(1\) 的个数为 \(k\) 个,我们只需在 check 时求出所有的 \(a_i - b_i \times L\),然后从大到小排序一遍,选取前 \(k\) 个,判断是否 \(\geq 0\) 即可。

code(有限制个数的)

【数论】0 / 1 分数规划

原文:https://www.cnblogs.com/chzhc-/p/13695339.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!