algorithm - 貪欲なアルゴリズム最適化

Question

次の問題があります。

• n 個のプロジェクトがあるとします。
• プロジェクト i に x 単位の時間を費やした場合に得られるポイント数を Fi(x) とします。
• T 単位の時間を使用して、任意のプロジェクトに取り組むことができます。

目標は、獲得するポイント数を最大化することであり、F 関数は減少しません。

F 関数の限界利益は減少します。つまり、特定のプロジェクトに x+1 単位の時間を費やすと、プロジェクトに x 単位の時間を費やすよりも、そのプロジェクトから得られる合計ポイントの増加が少なくなります。

次の O(nlogn + Tlogn) アルゴリズムを思いつきましたが、O(n + Tlogn) で実行されるアルゴリズムを見つけることになっています。

sum = 0
schedule[]
gain[] = sort(fi(1))

for sum < T
    getMax(gain) // assume that the max gain corresponds to project "P"
    schedule[P]++
    sum++
    gain.sortedInsert(Fp(schedule[P] + 1) - gain[P])
    gain[P].sortedDelete()

return schedule

つまり、初期ゲイン配列を並べ替えるには O(nlogn) が必要であり、ループを実行するには O(Tlogn) が必要です。私はこの問題について、認めようと思っている以上に考え抜いたので、O(n + Tlogn) で実行できるアルゴリズムを思いつくことができませんでした。