和の比率の最大化

長さNの正の数列 Ai, Bi からK個選んでSとする。ABそれぞれの和の比率を最大化したいとする

$arg max_{S} \frac{\sum _{i \in S} B _{i}}{\sum _{i \in S} A _{i}}$

和の比率を直接最大化するのではなく、和の比率がX以上かどうかの判定問題にし、Xを二分探索する解法がある

$\frac{\sum B _{i}}{\sum A _{i}} \geq X$
$\sum B_{i} \geq X \sum A_{i}$
$\sum B_{i} - X \sum A_{i} \geq 0$
$\sum (B_{i} - X A_{i}) \geq 0$ 条件を満たすSが存在するなら、 $B_{i} - X A_{i}$ が大きい方からK個選んだものは条件を満たす。よってこの判定問題はO(NlogN)で解ける。

このXを二分探索すれば、条件を満たすSがある最大のXが求まる。これはXの最大値である。

🪴 Quartz 4.0