分割整數數組到3個塊平等和

Question

不知道我的話來說不錯，但我會盡力在這裏進一步解釋：

所以，我有數字的數組，讓我們說1 2 3 4 5 6 7 8 9 10 11 14，我需要編寫一個算法將數組拆分成3個大小相同的數組，並且數目相等，在這種情況下，這將是：

{14,2,4} {11,6,3} {10,1,9} {5,7,8} - 我想我明白了。

所以，我現在已經在我的頭：

檢查整數的每一個可能的總和，並把使用了三個指標，將總和的結構。

然後，用一個結構數組，我將按總和對它們進行排序，並搜索N/3的總和數，如果找到，我會根據它們的索引打印出數字。

該算法包括很多次遍歷所有數字，所以它會很慢。任何人都可以提出更好的算法？如果有人想提供代碼段，我可以編程在C，我已經開始學習Java。

謝謝！

Answer 1

你不會說如果你總是打算用12個數字開始。

您有數字的下面的數組：1 2 3 4 5 6 7 8 9 10 11 14

1. 號數組的計數必須由3.整除如果不是，就沒有解。

2. 求和數組的數組。在這種情況下，總和爲80.

3. 我們有12個數字，所以我們有4個組3.將總和除以組數，即80/4或20。 t產生一個整數，沒有解決方案。

4. 經過數字，三個數字的時間，一旦，並保持三聯體的陣列，其總和爲20可以使用一個12位的二進制整數，起始於零和遞增1，以選擇三胞胎。當二進制整數有3位時，使用這些位的位置作爲數組數組的索引。

5. 檢查是否存在三元組的組數，並使用數組中的所有數字。如果是這樣，你有你的解決方案。如果沒有，沒有解決方案。

編輯補充：事實證明，有對這個問題給出數字的數組4個解決方案：

(2,4,14); (3,6,11); (1,9,10); (5,7,8) 
(2,4,14); (1,8,11); (3,7,10); (5,6,9) 
(1,5,14); (3,6,11); (2,8,10); (4,7,9) 
(1,5,14); (2,7,11); (4,6,10); (3,8,9) 

我寫的代碼只是爲了看看它會需要多長時間才能產生一個辦法。它跑了不到一秒鐘。

Answer 2

嗯，這是一個難題。編寫它的代碼有點困難，如果你有很多數字，解決它可能需要很長時間。

首先檢查一下解決方案是否可行。你有12個數字（如果它是11或13，你不能把它們分成3組），所以你需要4組3個。總數是80，這也很好，因爲你現在需要四組三個數字相加每個20個;如果總數是79或78，那就行不通了。

按降序對數字進行排序。最大的數字必須在一些組中，所以從14開始：14可以與5,1或4,2組合。你檢查兩種可能性。

下一個最大的數字必須在某個組中，所以我們取11。它可以與8,1或7,2或6,3或5,4組合。如果第一組是（14,5,1），那麼第二組可以是（11,7,2）或（11,6,3）。如果第一組是（14,4,2），那麼第二組可以是（11,8,1）或（11,6,3）。所以你的選擇不會增長太多。

所以你可以編寫一個遞歸函數，每次添加一個組;你添加的每個組包含最大的剩餘數字，加上兩個數字，總和最多爲20;你必須刪除你已經選擇的號碼。這是粗略的想法。

Answer 3

（粗略草圖）動態編程方法：

有3個整數的數組。有一個方法可以將整數標記爲已使用。將第一個未標記的數字添加到數組中並將其標記爲已使用。添加下一個沒有標記的號碼，看看這個總和是否仍然低於目標總和（你知道如何得到它）。否則請嘗試其他號碼。找出丟失的號碼並尋找它（確保它沒有標記）。假設你找到了它。你將擁有你的三胞胎（你已經將它存儲在某個地方，這是我不會簡單介紹的那部分）。尋找另一個三胞胎。

在將每個數字添加到三元組後，遞歸查找下一個數字，以便您可以返回並嘗試另一個組合，如果這個組合不起作用。它的工作原理是，在某些時候你可能會到達數組的末尾而不構建三元組。然後，您必須返回遞歸調用以嘗試其他編號。

只有您能夠標記所有數字，您才完成。

這裏肯定有改進的餘地，但如果你明白什麼是動態規劃，你應該明白。