和の比率の最大化
長さNの正の数列 Ai, Bi からK個選んでSとする。ABそれぞれの和の比率を最大化したいとする
\argmax_S { \sum_{i\in S} B_i \over \sum_{i\in S} A_i }
和の比率を直接最大化するのではなく、和の比率がX以上かどうかの判定問題にし、Xを二分探索する解法がある
{\sum B_i \over \sum A_i} \ge X
\sum B_i \ge X \sum A_i
\sum B_i - X \sum A_i \ge 0
\sum (B_i - X A_i) \ge 0
条件を満たすSが存在するなら、B_i - X A_i が大きい方からK個選んだものは条件を満たす。
よってこの判定問題はO(NlogN)で解ける。
このXを二分探索すれば、条件を満たすSがある最大のXが求まる。これはXの最大値である。
Related Pages
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]