和の比率の最大化

長さ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の最大値である。

濃度の最大化