天龍國生產一種蜜蘋果,體積碩大,甜度破表,是其國家主要的收入來源。每一顆蘋果的重量(w)不一樣,因甜度不同而售價(v)也有所不同,
今有 N 個蘋果,試求從中任意取出 K 個蘋果,使其<單位重量的售價>為最大。
<單位重量的售價> = <K 個蘋果的售價總和> / <K 個蘋果的重量總和>
範例: N=3, M=2, {w,v} --> {(5,5), (10,7), (8,6)}
k=2
選 (5,5)、(8,6) 兩個 --> (5+6)/(5+8)≅0.85 為最大值
k=1
選 (5,5) --> 5/5=1.00 為最大值