以下の（非現実的！）投資問題を検討してください。

Question

以下の（非現実的！）投資問題を考えてみましょう。

私たちは潜在的な投資の集合Sを持っており、それぞれが浮動小数点数の組（金額、推定収益率）で与えられます。投資する総額はAです。この金額の利益を最大限に生かすために投資を選択したいと考えています。

一つは、支出は（A）* F、および（Fの* rを取得（全体として各投資（r）を選択すること（のすべてを費やし、そしてRリターンを得る）、またはのみのみ割合fを選択することができます）return）。選択セットの推定リターンは、個々の選択のリターンの合計です。明らかに、Sの要素を選択する際には、利用可能な総量A以上を使うことはできません。

金額Aと投資額Sで実現できる最大予想収益率を計算するための効率的なアルゴリズムを記述します。アルゴリズムの時間複雑度は何ですか（ビッグ・オ表記）。

これは可能なのですか？

あなたのアルゴリズムを単語および/または擬似コードで記述するとよいでしょう。プログラミング言語でコードを組み込む必要はありません。

Answer 1

fractional knapsack problemです。これは整数の対応とは異なり、貪欲なアルゴリズムで最適な解を解決するのは幸運にも簡単です。

1. スタート減少比rに応じて投資を注文することによって/
2. は、このような順番で投資にご利用できる資金を割り当てます。私。すべての最初の投資を買ってから、2番目の投資を買うために利用可能な資金を使い、3番目の資金を買って、お金を使い終えるまで。

複雑さについては、比率を計算するためのO（n）、投資をソートするためのO（n logn）、お金を割り当てるためのO（n）があります。これは、全体のアルゴリズムがO（n logn）であることを意味します。