最大化平均值 ( binary search )

最大化平均值 ( binary search )

有 $n$ 個 物 品 每 個 物 品 都 有 其 價 值 ( $n_v$ ) 與 重 量 ( $n_w$ ) 。 選 $k$ 個，要 求 平 均 值 (總 值 / 總 重) 最 大 。

假 設 $x$ 為 目 前 理 想 平 均 值，而 我 們 選 的 物 品 為 集 合 $S$。

那 平 均 值 則 為 $\sum$ $S_v$ $/$ $\sum$ $S_w$，判 斷 是 否 存 在 $\sum$ $S_v$ $/$ $\sum$ $S_w$ $>=$ $x$，將 此 不 等 式 做 變 化 :
$\sum$ $S_v$ - $x$ $*$ $\sum$ $S_w$ $>=$ $0$

就 可 以 對 $S_v$ - $x$ $*$ $S_w$ 做 排 序，再 用 greedy 進 行 選 取。

而 $x$ 可 以 用 二 分 搜 尋 找 到 最 佳 解。

code: