algorithm - 贪心算法优化

Question

我有以下问题:

• 设n个项目。
• 令 Fi(x) 等于您花费的积分数x 单位时间在项目 i 上工作。
• 你有 T 个单位的时间来使用和处理任何你想做的项目喜欢。

目标是最大化您将获得的分数，并且 F 函数是非递减的。

F 函数的边际 yield 递减，换句话说，在特定项目上花费 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

对于第一种情况，使用堆，构造堆需要O(n)时间，每次ExtractMin & DecreaseKey函数调用需要O(logN)时间。

对于第二种情况，构造一个 nXT 表，其中第 i 列表示情况 T=i 的解决方案。第 i+1 列应仅取决于第 i 列的值和函数 F，因此可在 O(nT) 时间内计算。我没有彻底考虑所有情况，但这应该给你一个良好的开端。