Split array into half with equal or approximately equal array sum

Question

Problem:

Array with numeric values needs to be split in half with approximately equal or if possible equal array sum. Number or order of elements in arrays is not important.

$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 

Any suggestions?

Thanks.

Answer 1

Like this?

<?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);

Answer 2

Are you aware that this is the http://en.wikipedia.org/wiki/Knapsack_problem ?

And it's NP-Complete, so you can't do it fast.

For a small list it won't be too bad, if you have a larger list see some of the solutions on the wikipedia page.