时间戳

首页 > 解决方案 > Split an array into three similar Sum

php - Split an array into three similar Sum

问题描述

I would like to split an array into three array that have similar sums - as close as possible

I have array 

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

Desire output for example:

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

Thanks

标签： phparrayspartitioning

解决方案

您可以使用以下算法：

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

考虑以下代码：

$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

推荐阅读