algorithm - 总权重W的非重叠区间的最大总和

Question

给定一个 N 整数序列 S 和一个正整数 W，找到一组不重叠的区间，使得它们的总权重恰好是 W 并且它们的总和最大化。

For a chosen interval [i,j]:

 - Weight([i,j]) = j-i+1 
 - Sum([i,j]) = S[i+1] + S[i+2] + ... + S[j].

例子

S = (12, 9, 1, 2, 8, -1), W = 4  

Choose [1,2] and [4,5] with total_sum = Sum([1,2]) + Sum([4,5]) = 9 + 8 = 17

(12 9 _ 2 8 _)

这个问题听起来有点像背包问题和加权区间调度，但我认为这可以用更简单的方法解决。

我的想法是使用动态规划，让 P[i][k] 是前 i 个元素的最大总和，只使用 k 个元素，答案是 P[N][W]，但我想不出子问题之间的关系。

Answer 1

如果你从左到右工作，你可以总结到目前为止的答案:

1)它的重量

2) 该答案中最右边区间的右端

3)其区间内的元素之和

所以我认为你可以通过从左到右运行的动态程序来解决这个问题，如果在每个阶段，对于最右边区间的右端和总权重的每个可能组合，你都跟踪具有最大总和的答案。