将数组拆分为三个相似的 Sum

Question

我想将一个数组分成三个总和相似的数组 - 尽可能接近

我有数组

$arr = [1,2,4,7,1,6,2,8];

期望输出例如：

a = 8,2 // as sum is 10
b = 7,2,1 // as sum is 10
c = 6,4,1 // as sum is 10

谢谢

Answer 1

您可以使用以下算法：

将输入数组从大到小排序
创建输出数组
对于输入中的每个元素 - 插入到输出数组中的最低总和。

考虑以下代码：

$arr = [1,2,4,7,1,6,2,8];
sort($arr);
$arr = array_reverse($arr); // big to small
$out = array(array(),array(),array()); // output array

for($i = 0; $i < 8; $i++) {
    $sums = array_map("array_sum" ,$out); // get all current sums of the array 
    $index = array_keys($sums, min($sums))[0]; // get the min sum
    $out[$index][] = $arr[$i]; // add the element to the array with the lowest sum 
}

echo print_r($out, true);

现在您将获得：

array:
  [0]: array:
         [0] => 8
         [1] => 2
         [2] => 1
  [1]: array:
         [0] => 7
         [1] => 2
         [2] => 1
   [2]: array:
         [0] => 6
         [1] => 4

将数组拆分为三个相似的 Sum

Split an array into three similar Sum

php

arrays

partitioning