貪心算法優化

Question

我有以下問題：

• 讓那裏是n的項目。
• 讓Fi（x）等於您在項目i上花費 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）。

Answer 1

對於第一種情況，使用Heap，構造堆將花費O（n）時間，並且每個ExtractMin DecreaseKey函數調用將花費O（logN）時間。

對於第二種情況，構造一個nXT表，其中第i列表示案例T = i的解。第i + 1列應該僅取決於第i列和函數F的值，因此可以在O（nT）時間內計算。我沒有徹底思考所有的情況，但這應該會給你一個好的開始。