2

给定一个整数序列S和N一个正整数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 _)

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

我的想法是使用动态编程和 let P[i][k] be the maximum total sum of the first i elements, using only k elements，答案是P[N][W]，但我想不出子问题之间的关系。

4

2 回答 2

1

如果您从左到右工作，您可以通过以下方式总结到目前为止的答案：

1) 重量

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

3) 其区间内的元素之和

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

于 2013-03-10T13:36:59.177 回答
0

不应该是：

  f[i][j]= MAX( f[i-1][j] , f[i-T][j-Weight[i-T,i]]+Sum[i-T,i] );

然后你得到答案f[N][W]。我很确定应该有某种方法可以将这个O(N^2W)解决方案优化为一个更好的解决方案。但既然你没有要求更快的...

于 2013-03-10T13:53:49.327 回答