sorting - n 個の潜在的な投資の集合 S がある

Question

n 個の潜在的な投資のセット S があり、それぞれが浮動小数点数のペア (金額、推定収益) によって与えられます。投資する合計金額 A があります。この金額の収益を最大化する投資を選択したいと考えています。

nlogn で、推定リターン/金額の比率を使用して投資を注文する方法を説明してください。これはクイックソートを使用していますか？O(n) で比率を計算できますが、どの比率がどの投資に属しているかを示す指標をどのように保持すればよいでしょうか?

Answer 1

ナップザック問題の一種ではないでしょうか？通常、この種の問題は動的計画法を使用して解決されます。StackOverflowのトピックを含め、Web 上にいくつかの 例があります。