3

我收到了一份动态规划作业，我需要帮助找出递归关系。该问题类似于加权区间问题，但它有一些额外的限制：

  • 给你一系列N时间段，每个时间段都相同。
  • 每个时隙k,0 <= k < N都被赋予一个正权重W[k]。
  • 对于任何具有 的时间间隔[i, j]，该间隔i < j的权重为： 请注意，不计算第一个时隙的权重，因此任何长度间隔的权重为。W[i,j]
    W[i,j] = W[i+1] + W[i+2] + ... + W[j]
    W[i]10

给您一个值T < N并要求您准确选择T时间段，以使所选时间间隔的总和最大化。

示例：对于N = 5和T = 4权重W = (3, 9, 1, 1, 7)，选择W[0, 1] = 9和W[3, 4] = 7将给出最大权重16。

4

1 回答 1

5

这是一个很好的小问题......如果选择的最后一个插槽（最后一个范围的结尾）是 i 并且在插槽 0..i 中恰好选择了 t 个插槽，则将 S(i, t) 定义为可能的最大权重。

DP 决定是我们要么将 w[i] 添加到 S(i, t) 中，要么不添加，因为要么选择了插槽 i-1，要么没有选择。所以我们有：

S(i, t) = max ( S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2 )

t-1>i 的情况是没有意义的。所以基本情况是 S(i, 1) = 0 for 0 <= i < N，并且 DP 表的连续列 (t = 2,...,T) 每列都比最后一列短。所需的答案是 max ( S(j, T) for j = T-1..N-1 )

令人高兴的是，您可以安排计算，以便增量计算最大值，运行时间为 O(NT)，空间为 O(N)

制定您的示例，DP 表如下所示：

               t = 
         1    2    3    4
       ------------------
i = 0 |  0
    1 |  0    9   
    2 |  0    1   10
    3 |  0    1    9   11
    4 |  0    7    9   16

答案是 max(11, 16) = 16

于 2013-03-09T18:59:46.490 回答