将数组分成两半，使得每一半的元素之和相等或近似相等

Question

将数组分成两半，使得每一半的元素之和相等或近似相等

3

问题：

需要将具有数值的数组分成两半，使得两个数组的和尽可能相等，或者完全相等。数组中元素的数量或顺序并不重要。

$probabilites = array(0.4, 0.15, 0.1, 0.1, 0.2, 0.2, 0.3); # 1.45

$probabilites[0] = array(0.4, 0.15, 0.1, 0.1); # 0.75
$probabilites[1] = array(0.2, 0.2, 0.3); # 0.7

有什么建议吗？

谢谢。

- Dejan Marjanović

给定的顺序应该保持吗？例如 array(0.4, 0.15, 0.2) 和 array(0.2, 0.1, 0.1, 0.3) 是有效的吗？（如果是，我想这会使事情变得更加复杂。） - jensgram

@jensgram，我写道这一点根本不重要，只要两个数组的总和尽可能接近即可。是的，这是有效的，我们不能将7个元素分成一半，4 + 3是理想的。MarvinLabs，~= :) 你可以看到在例子中，0.75接近于0.7，反之亦然。 - Dejan Marjanović

我的第一次尝试的大O复杂度非常糟糕。 - cwallenpoole

4个回答

3

您是否了解这是背包问题？

而且它是NP完全问题，所以您无法快速解决它。

对于小型列表，情况不会太糟糕，如果您有一个更大的列表，请查看维基百科页面上的一些解决方案。

- Ariel

谢谢您提供的链接，基本上就是这样了。数组中最多只有几十个值，总和为1。 - Dejan Marjanović

0

尝试以下步骤：

从一个空的数组A和给定的数组B（在你的例子中为 $probabilities）开始：

移除B的第一个元素并将其添加到A中。
计算两个数组的总和并计算它们的差值。
重复以上步骤，直到差值变得更糟。
当差值变得更糟（即变大）时，撤销最后一步操作即可完成。

或者为了节省时间：

首先计算B的总和=sum0。
移除B的第一个元素并将其添加到A中。
将sum（a）与sum0 / 2进行比较。
重复以上步骤，直到差值变得更糟并撤销最后一步操作。

- Hyperboreus

不，这并不总是有效。想象一下数值为0.1、0.1、0.1、10、0.1、0.1、0.1的情况。最好的方法是将10放在一个数组中，将所有六个0.1条目放在另一个数组中。您的算法将使您在数组一中得到0.1、0.1、0.1，在数组二中得到10、0.1、0.1、0.1。 - Pelle

由于 OP 保持了原始数组的顺序，所以我也遵循了他的例子。 - Hyperboreus

谢谢您的输入，我尝试过类似的方法，但我确信还有其他方法。Pelle ten Cate提供了非常好的解决方案。对于顺序问题，我很抱歉，那只是巧合。再次感谢您。 - Dejan Marjanović

好吧，我想，如果只是为了这个例子，我会手动完成它。感谢TS与我达成一致，我认为其他数字列表也会出现。 :) - Pelle

是的，你的方法肯定更复杂，拆分效果也比我的好。除非你得到一个像(2, 3, -5)这样的数组。这将产生(2, -5)和(3)。但是在这种情况下，我的方法也会失败。 - Hyperboreus

0

也许可以对数组进行排序，从最大值开始。将其他值放入两个数组之一，使它们的总和较小。有人可以检查这个解决方案吗？

- Piotr Müller

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pelle · Accepted Answer

像这样吗？

<?php
$in = array(0.4, 0.15, 0.1, 0.1, 0.2, 0.2, 0.3);

// Sort array decreasing
rsort($in, SORT_NUMERIC);

// Start with two empty arrays
$arr1 = $arr2 = array();

// Put the next value in the array in the array with the lowest sum
foreach ($in as $value)
  if (array_sum($arr2) > array_sum($arr1)) $arr1[] = $value; else $arr2[] = $value;

// Wrap in array (as in question)
$out = array($arr1,$arr2);