动态规划工作分配算法

Question

问题是这样的:

需要执行 n 个工作，每个工作都有一个增益 {v1, v2,. . . , vn}, 其实现所需的时间 {t1, t2,. . . , tn} 及其实现期限 {d1, d2,. . . , dn} 且 d1<=d2<=.....<=d3。知道只有在那个时间完成工作并且您只有一台机器时才会获得 yield 。必须描述一种计算可能获得的最大增益的算法。

我想到了一个有两个参数的递归方程，一个表示第 i 个作业，另一个表示我们正在执行的时刻: OPT(i,d) ，如果 d+t_i <= d 然后添加获得 t_i。 (然后是多路选择的变体..对于 1<=i<=n 是最小值)。

我的主要问题是:如何找到以前执行过的工作？我用的数据结构支持吗？

正如您会写递推方程式那样？

谢谢你!!!!

Answer 1

我的主要问题是:我怎样才能找到以前完成的工作？我用的数据结构支持吗？
诀窍是，您不需要知道已经完成了哪些工作。因为您可以按照截止日期递增的顺序执行它们。

比方说，一些最佳解决方案(产生最大利润)要求您完成工作A(截止日期10)，然后是工作B(截止日期 3)。但在这种情况下，您可以安全地交换 A 和 B。它们仍将按时完成，新安排将产生相同的总利润。
证明结束。

你会写出递归方程吗？
您已经有了大致的想法，但不需要循环(min for 1<=i<=n)。

max_profit(current_job, start_time)
    // skip this job
    result1 = max_profit(current_job + 1, start_time)

    // start doing this job now
    finish_time = start_time + T[current_job]
    if finish_time <= D[current_job]
        // only if we can finish it before deadline
        result2 = max_profit(current_job + 1, finish_time) + V[current_job];
    end

    return max(result1, result2);
end

将其转换为 DP 应该是微不足道的。

如果您不希望O(n*max_deadline) 复杂性(例如，当d 和t 值很大时)，您可以用 memoization 求助于递归并将结果存储在哈希表而不是二维数组中。

编辑
如果所有的工作都必须完成，但不是所有的工作都会得到报酬，那么问题仍然存在。把你没有时间做的工作(你不能在截止日期前完成的工作)推到最后。就这样。