什麼是算法將一組項目分解爲3個獨立的組？

我的教科書中有這個問題：給定一組n個項目，每個項目都有一個不同的值V（i），將項目分成3組的最佳方式是什麼，所以具有最高值的組被最小化？給這個最大的團體的價值。什麼是算法將一組項目分解爲3個獨立的組？

我知道如何做這個問題的2堆變種：它只需要在問題上向後運行揹包算法。然而，我很困惑如何解決這個問題。任何人都可以給我任何指示？

答：幾乎是同樣的事情0-1揹包，雖然2D

2012-01-06 Richie Li

既然它出現並消失了，這裏就是一個貪心失敗的例子{100,51,49,40,30,20,10}。最佳答案是完美分割，貪婪地將最大未分配元素應用於最小分組不是。 – ccoakley 2012-01-06 19:13:53

我有同樣的教科書。布賴恩迪恩給了我;） – joshim5 2012-01-10 14:48:03

艱難的功課問題。這實質上是3分區問題的優化版本。

它是密切相關的裝箱，分區和子集和（，正如你提到的，揹包）。然而，它恰好是強烈的NP-Complete，這使它比堂兄弟更難。無論如何，我建議你首先看看動態編程解決方案的相關問題（我會從分區開始，但找到DP解決方案的非維基百科解釋）。

更新：我很抱歉。我誤導了你。 3分區問題將輸入分成3組，而不是3組。我所說的其餘部分仍然適用，但重新希望你的變體不是很強的np-complete。

2012-01-06 18:07:59 ccoakley

我已經添加了一些信息的問題。 – 2012-01-06 18:19:51

@RichieLi誠實的問題：你希望我有多少細節不會破壞這個問題？即期望的復發關係是否太多（不是我擁有它，我必須自己解決）？ – ccoakley 2012-01-06 18:23:00

嗯，我會盡力自己解決。它在晚上到期，所以如果我需要更多幫助，我會盡快回復您。 – 2012-01-06 18:28:49

我從數學角度不瞭解「The Best」，但一種顯而易見的方法是在每個組中最初建立一組項目。然後，只要您的組的數量多於期望數量的最終組，請提取具有最低值的兩個組，然後將它們合併爲一個新組，並添加回集合中。這與霍夫曼壓縮樹如何構建相似。

實施例：

1 3 7 9 10 
becomes 
4(1+3) 7 9 10 
becomes 
9 10 11(1+3+7)

2012-01-06 18:12:51

我們還沒有了解到這一點，所以我不認爲我應該在這個問題上使用它。 – 2012-01-06 18:15:28

採摘尼特：貪婪方法在霍夫曼情況下是最優的（對於固定字母的可變長度編碼）。只有當問題中的數字分佈得很好時（我不能比「很好地」這個詞更精確），它才能合理地進行分區。鑑於這個問題被標記爲「動態編程」，我猜測這個任務的目的不是使用貪婪技術。 – ccoakley 2012-01-06 18:17:25

設f [i] [j] [k]表示是否有可能具有在所述第一組值j和在第二組值k，與第一個項目。

所以我們有f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]]。我們有f[0][0][0] = True。

對於每f[i][j][k] = True，更新你的答案取決於你如何定義相當。

2012-01-08 04:02:21 Topro

但是第i個項目也可以進入第3個集合，所以我認爲它應該是f [i] [j] [k] = f [i-1] [jv [i]] [k]或f [i -1] [j] [kv [i]]或f [i-1] [j] [k]'。 – 2012-12-18 16:26:52

另外，爲了解釋它，當考慮一些i，j，k的解，其中f [i] [j] [k] = True時，可以使用s [i] - j來計算第三組的權重 - k，其中s [i]是前i項的權重之和（以開始時的線性時間進行預先計算）。 – 2012-12-18 16:28:16

@j_random_hacker是的，你是對的。我的錯 – Topro 2012-12-19 04:50:33

回答