algorithm - 具有可变权重的加权间隔调度

Question

在传统的加权区间调度问题中，我们有一个区间列表{i_1, ..., i_n}，权重为w_j。给出了解决加权区间调度问题的算法here是一个基本的动态规划问题。但是，如果在一个调度表中，所选区间的权重取决于它之前的区间的权重(反过来，权重取决于顺序)，会发生什么情况？一个示例是 w_j' = w_j'*(w_(j-1)' + 1)，其中引数变量是固有权重，非引数变量是考虑顺序的“实际”权重，即您实际用于目标函数的那些。这个问题是NP难的吗？听起来确实像。

编辑:为了使这更容易(也更现实)，让我们假设离散的单位时间。

Answer 1

好吧，我明白了。算法为(如有错误请指正):

for t in times:
    if is_first(t):
        best_candidate = None
    else:
        best_candidate = best(t - 1)

    for interval in intervals if interval.end_time is t:
        value_i = f(best(interval.start_time) + interval)
        value_candidate = f(best_candidate)
        if value_i > value_candidate:
            best_candidate = best(interval.start_time) + interval

    best(t) = best_candidate

return best(times[-1])

其中集合 times, intervals 是间隔的潜在时间停止和间隔本身，f 是目标函数。

迭代之间的常数是:随着时间t的迭代结束后，best(t)就是以t结束的最佳调度>。请注意，由于初始化步骤，best(t) == best(t - 1) 是可能的。另请注意，如我的评论所述，这仅在 f 单调递增时才有效，因为 f 旨在根据其之前的间隔应用于每个单独的间隔。我以这里的方式使用它作为速记。