非重疊間隔與總重量的最大總和W

給定N整數的一個序列S和一個正整數W，找到一組不重疊的間隔，以使它們的總重量恰好爲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] be the maximum total sum of the first i elements, using only k elements和答案是P[N][W]，但我不能提出子問題之間的關係。

來源

2013-03-10 jayus

儘管在「間隔」方面的措辭，權重函數根本不依賴於「間隔結構」，因爲任何分裂方式將一些區間[i，j]劃分爲子區間（包括將每個j-i + 1個元素作爲一個單獨的長度爲1的區間），在總和它們的權重之後，答案是相同的。重量等於所選項目總數，所以這實際上是揹包問題的一個特例，其中每個項目的重量都是1。 – 2014-06-26 05:23:38

如果你從左工作的權利，你可以指出，到目前爲止總結的答案：

1）它的重量

2）最右邊的間隔在回答右端

3 ）在它的時間間隔中的元素總和

所以我認爲你可以解決這個問題，如果在每個階段，對於右端間隔和總重量的每個可能的組合，你可以保持動態程序從左到右運行跟蹤的答案與最大的總和。

來源

2013-03-10 13:36:59 mcdowella

它不應該是：

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-10 13:53:49 phoeagon

非重疊間隔與總重量的最大總和W

回答

相關問題