分割整数数组到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个整数的数组。有一个方法可以将整数标记为已使用。将第一个未标记的数字添加到数组中并将其标记为已使用。添加下一个没有标记的号码，看看这个总和是否仍然低于目标总和（你知道如何得到它）。否则请尝试其他号码。找出丢失的号码并寻找它（确保它没有标记）。假设你找到了它。你将拥有你的三胞胎（你已经将它存储在某个地方，这是我不会简单介绍的那部分）。寻找另一个三胞胎。

在将每个数字添加到三元组后，递归查找下一个数字，以便您可以返回并尝试另一个组合，如果这个组合不起作用。它的工作原理是，在某些时候你可能会到达数组的末尾而不构建三元组。然后，您必须返回递归调用以尝试其他编号。

只有您能够标记所有数字，您才完成。

这里肯定有改进的余地，但如果你明白什么是动态规划，你应该明白。