2

我有以下问题：

  • 假设有 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) 中运行的算法。

4

1 回答 1

1

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

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

于 2012-11-22T19:31:32.923 回答