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

Question

Hi Guys,

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

Without knowing if this is a homework assignment or not, I can give you some pseudo code as a hint for a possible solution, note the solution is not very efficient, more of a demonstration.

Hint:

Compare each field value to all field value and at each iteration check if their sum is equal to TOTAL_AMOUNT.

Pseudo code:

for i through field  1-20
 for j through field 1-20
   if value of i + value of j == total_amount
        return i and j

Update:

As stereofrog as pointed out, what you seem to be having is the Subset sum problem, given within the Wiki link is pseudo code for the algorithm which might help point you in the right direction.

Answer 2

1. Check and eliminate fields values more than 21st field

2. Check highest of the remaining, Add smallest, 

3. if its greater than 21st eliminate highest (iterate this process)

   4. If lower: Highest + second Lowest, if equal show result.

   5. if higher go to step 7

   6. if lower go to step 4

7. if its lower than add second lowest, go to step 3.

8. if its equal show result

This is efficient and will take less execution time.

Answer 3

i don't think the answer isn't as easy as nik mentioned. let's ay you have the following numbers:

1 2 3 6 8

looking for an amount of 10

niks solution would do this (if i understand it right):

1*8 = 9 = too low
adding next lowest (2) = 11 = too high

now he would delete the high number and start again taking the new highest

1*6 = 7 = too low
adding next lowest (2) = 9 = too low
adding next lowest (3) = 12 = too high

... and so on, where the perfect answer would simply be 8+2 = 10... i think the only solution is trying every possible combination of numbers and stop if the amaunt you are looking for is found (or realy calculate all, if there are different solutions and save which one has used least numbers).

EDIT: realy calculating all possible combiations of 21 numbers will end up in realy, realy, realy much calculations - so there must be any "intelligent" solution for adding numbers in a special order (lik that one in niks post - with some improvements, maybe that will bring us to a reliable solution)

Answer 4

Following method will give you an answer... almost all of the time. Increase the iterations variable to your taste.

<?php

// Inputs
$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;

// Let's try to do this a million times randomly
// Relax, thats less than a blink
$iterations=1000000;
while($iterations-->0){
    $z=array_rand($n, mt_rand(2,20));
    $total=0;
    foreach($z as $x) $total+=$n[$x];
    if($total==$t)break;
}

// If we did less than a million times we have an answer
if($iterations>0){
    $total=0;
    foreach($z as $x){
        $total+=$n[$x];
        print("[$x] + ". $n[$x] . " = $total<br/>");
    }
}

?>

One solution:

[1] + 8.99 = 8.99
[4] + 8.16 = 17.15
[5] + 2.53 = 19.68
[6] + 0.28 = 19.96
[8] + 0.34 = 20.3
[10] + 8.24 = 28.54
[11] + 4.35 = 32.89
[13] + 1.69 = 34.58
[14] + 5.64 = 40.22
[15] + 0.27 = 40.49
[16] + 2.73 = 43.22
[17] + 1.63 = 44.85
[18] + 4.07 = 48.92
[19] + 9.04 = 57.96

Answer 5

sorry for adding a new answer, but this is a complete new solution which solves all problems of life, universe and everything... simply use this function i wrote:

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

Answer 6

A probably inefficient but simple solution with backtracking

function subset_sums($a, $val, $i = 0) {
    $r = array();
    while($i < count($a)) {
        $v = $a[$i];
        if($v == $val)
            $r[] = $v;
        if($v < $val)
            foreach(subset_sums($a, $val - $v, $i + 1) as $s)
                $r[] = "$v $s";
        $i++;
    }
    return $r;
}

example

$ns = array(1, 2, 6, 7, 11, 5, 8, 9, 3);
print_r(subset_sums($ns, 11));

result

Array
(
    [0] => 1 2 5 3
    [1] => 1 2 8
    [2] => 1 7 3
    [3] => 2 6 3
    [4] => 2 9
    [5] => 6 5
    [6] => 11
    [7] => 8 3
)

Answer 7

Hey at all,

i've just checked the funktion which was posted by oezi. I think, it's the best and fastest way to do it. I have to post this as Answer becuase i'm not allowed to write comments yet. ;)

Answer 8

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 to 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 slower!

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. Floats comparison shall never be used, 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);