PHP: find two or more numbers from a list of numbers that add up towards a given amount

Question

I am trying to create a little php script that can make my life a bit easier. Basically, I am going to have 21 text fields on a page where I am going to input 20 different numbers. In the last field I will enter a number let's call it the TOTAL AMOUNT. All I want the script to do is to point out which numbers from the 20 fields added up will come up to TOTAL AMOUNT.

Example:

field1 = 25.23
field2 = 34.45
field3 = 56.67
field4 = 63.54
field5 = 87.54
....
field20 = 4.2

Total Amount = 81.90

Output: field1 + fields3 = 81.90

Some of the fields might have 0 as value because sometimes I only need to enter 5-15 fields and the maximum will be 20.

If someone can help me out with the php code for this, will be greatly appreciated.

Answer 1

If you look at oezis algorithm one drawback is immediately clear: It spends very much time summing up numbers which are already known not to work. (For example if 1 + 2 is already too big, it doesn't make any sense to try 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ..., too.)

Thus I have written an improved version. It does not use bit magic, it makes everything manual. A drawback is, that it requires the input values to be sorted (use rsort). But that shouldn't be a big problem ;)

function array_sum_parts($vals, $sum){
    $solutions = array();
    $pos = array(0 => count($vals) - 1);
    $lastPosIndex = 0;
    $currentPos = $pos[0];
    $currentSum = 0;
    while (true) {
        $currentSum += $vals[$currentPos];

        if ($currentSum < $sum && $currentPos != 0) {
            $pos[++$lastPosIndex] = --$currentPos;
        } else {
            if ($currentSum == $sum) {
                $solutions[] = array_slice($pos, 0, $lastPosIndex + 1);
            }

            if ($lastPosIndex == 0) {
                break;
            }

            $currentSum -= $vals[$currentPos] + $vals[1 + $currentPos = --$pos[--$lastPosIndex]];
        }
    }

    return $solutions;
}

A modified version of oezis testing program (see end) outputs:

possibilities: 540
took: 3.0897309780121

So it took only 3.1 seconds to execute, whereas oezis code executed 65 seconds on my machine (yes, my machine is very slow). That's more than 20 times faster!

Furthermore you may notice, that my code found 540 instead of 338 possibilities. This is because I adjusted the testing program to use integers instead of floats. Direct floating point comparison is rarely the right thing to do, this is a great example why: You sometimes get 59.959999999999 instead of 59.96 and thus the match will not be counted. So, if I run oezis code with integers it finds 540 possibilities, too ;)

Testing program:

// Inputs
$n = array();
$n[0]  = 6.56;
$n[1]  = 8.99;
$n[2]  = 1.45;
$n[3]  = 4.83;
$n[4]  = 8.16;
$n[5]  = 2.53;
$n[6]  = 0.28;
$n[7]  = 9.37;
$n[8]  = 0.34;
$n[9]  = 5.82;
$n[10] = 8.24;
$n[11] = 4.35;
$n[12] = 9.67;
$n[13] = 1.69;
$n[14] = 5.64;
$n[15] = 0.27;
$n[16] = 2.73;
$n[17] = 1.63;
$n[18] = 4.07;
$n[19] = 9.04;
$n[20] = 6.32;

// Convert to Integers
foreach ($n as &$num) {
    $num *= 100;
}
$sum = 57.96 * 100;

// Sort from High to Low
rsort($n);

// Measure time
$start = microtime(true);
echo 'possibilities: ', count($result = array_sum_parts($n, $sum)), '<br />';
echo 'took: ', microtime(true) - $start;

// Check that the result is correct
foreach ($result as $element) {
    $s = 0;
    foreach ($element as $i) {
        $s += $n[$i];
    }
    if ($s != $sum) echo '<br />FAIL!';
}

var_dump($result);

Answer 2

sorry for adding a new answer, but this is a complete new solution to solve all problems of life, universe and everything...:

function array_sum_parts($n,$t,$all=false){
    $count_n = count($n); // how much fields are in that array?
    $count = pow(2,$count_n); // we need to do 2^fields calculations to test all possibilities

    # now i want to look at every number from 1 to $count, where the number is representing
    # the array and add up all array-elements which are at positions where my actual number
    # has a 1-bit
    # EXAMPLE:
    # $i = 1  in binary mode 1 = 01  i'll use ony the first array-element
    # $i = 10  in binary mode 10 = 1010  ill use the secont and the fourth array-element
    # and so on... the number of 1-bits is the amount of numbers used in that try

    for($i=1;$i<=$count;$i++){ // start calculating all possibilities
        $total=0; // sum of this try
        $anzahl=0; // counter for 1-bits in this try
        $k = $i; // store $i to another variable which can be changed during the loop
        for($j=0;$j<$count_n;$j++){ // loop trough array-elemnts
            $total+=($k%2)*$n[$j]; // add up if the corresponding bit of $i is 1
            $anzahl+=($k%2); // add up the number of 1-bits
            $k=$k>>1; //bit-shift to the left for looking at the next bit in the next loop
        }
        if($total==$t){
            $loesung[$i] = $anzahl; // if sum of this try is the sum we are looking for, save this to an array (whith the number of 1-bits for sorting)
            if(!$all){
                break; // if we're not looking for all solutions, make a break because the first one was found
            }
        }
    }

    asort($loesung); // sort all solutions by the amount of numbers used


    // formating the solutions to getting back the original array-keys (which shoud be the return-value)
    foreach($loesung as $val=>$anzahl){
        $bit = strrev(decbin($val));
        $total=0;
        $ret_this = array();
        for($j=0;$j<=strlen($bit);$j++){
            if($bit[$j]=='1'){
                $ret_this[] = $j;
            }   
        }
        $ret[]=$ret_this;
    }

    return $ret;
}

// Inputs
$n[0]=6.56;
$n[1]=8.99;
$n[2]=1.45;
$n[3]=4.83;
$n[4]=8.16;
$n[5]=2.53;
$n[6]=0.28;
$n[7]=9.37;
$n[8]=0.34;
$n[9]=5.82;
$n[10]=8.24;
$n[11]=4.35;
$n[12]=9.67;
$n[13]=1.69;
$n[14]=5.64;
$n[15]=0.27;
$n[16]=2.73;
$n[17]=1.63;
$n[18]=4.07;
$n[19]=9.04;
$n[20]=6.32;

// Output
$t=57.96;

var_dump(array_sum_parts($n,$t)); //returns one possible solution (fuc*** fast)

var_dump(array_sum_parts($n,$t,true)); // returns all possible solution (relatively fast when you think of all the needet calculations)

if you don't use the third parameter, it returns the best (whith the least amount numbers used) solution as array (whith keys of the input-array) - if you set the third parameter to true, ALL solutions are returned (for testing, i used the same numbers as zaf in his post - there are 338 solutions in this case, found in ~10sec on my machine).

EDIT: if you get all, you get the results ordered by which is "best" - whithout this, you only get the first found solution (which isn't necessarily the best).

EDIT2: to forfil the desire of some explanation, i commented the essential parts of the code . if anyone needs more explanation, please ask