选择哪些任务可以赚取尽可能多的钱

Question

我无法理解这个问题：

• 你有n个任务
• 每个任务需要时间t，它表示完成任务所需的时间（t[i]是完成第i个任务所需的时间）
• r[i]代表第i个任务的截止时间（我们从时间=0开始，r[i]是一个整数，表示任务必须在何时完成）
• 如果任务在截止时间之前完成，您将获得该任务的奖励p[i]
• 您需要计算通过完成这些任务可以获得的最大奖励
• 只有在满足截止时间的情况下才会给予奖励
• 所有值都是整数
• 解决方案必须尽可能地复杂度最低

我尝试应用贪心算法，但我发现该算法并不总是提供最优解。我可以编写一种暴力算法，但那不是重点。我认为可以使用动态规划，但我不知道如何做。

- user3362334

Answer 1

如果所有时间都相等，那么该系统可以被证明是一个拟阵，而贪心算法将给出最优结果（见Charles E. Leiserson、Thomas H. Cormen、Clifford Stein和Ronald Rivest的《算法导论》第16章）。

然而，假设时间不相等，在一般情况下，这种问题是NP难的。

要看到为什么，考虑所有截止日期都是固定值的情况。那么问题等价于找到将项目最佳地装入固定时间预算的方法，并等同于已知为NP完全问题的0/1背包问题。

在您的特定情况下，时间是整数，因此您可能能够采用0/1背包动态规划方法进行调整。

我建议尝试使用基于子问题f(t)的动态规划来解决此问题，其中f(t)是安排所有截止日期小于或等于t的任务的最小惩罚。

- Peter de Rivaz

---

谢谢您的建议，它很有帮助。我实际上是通过使用修改后的动态规划方法来解决背包问题的。 - user3362334

Answer 2

我使用动态规划解决了这个问题。 f[i] 表示你在第 i 小时可以获得的最大奖励。解决方案是 f[max(r)]，其中 max(r) 是截止日期中的最大值。

在我的解决方案中，您还需要一个列表 X[i]，其中 X[i] 表示您应该在第 i 小时完成的最佳任务列表以获得最大奖励。

以下是伪代码：

LIST x0...n = empty;  // x0, x1....xn are all different lists
f[0] = 0;
for i=1 to max(r) do
    max = f[i-1];
    x[i] = x[i-1];
    for j=1 to n do
        if t[j] <= i and r[j] >= i and j.isNotElementOf(x[f[i-t[j]]]) then
            reward = p[j] + f[i-t[j]];
            if reward > max then
                max = reward;;
                x[i] = x[i-t[j]];
                x[i].add(j);
    f[i] = max;
return f[max(r)];

- user3362334