PHP: find two or more numbers from a list of numbers that are added to a certain amount

Question

I am trying to create a small PHP script that can make my life easier. Basically, I will have 21 text boxes on the page where I am going to enter 20 different numbers. In the last field I enter the number, call it the TOTAL AMOUNT. All I want to do a script is to indicate which numbers of the 20 added fields will be displayed before 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 can have a value of 0, because sometimes I need to enter only 5-15 fields, and a maximum of 20.

If someone can help me with the PHP code for this, we will be very grateful.

Answer 1

If you look at the oezis algorithm , one of the drawbacks immediately becomes clear: it spends a lot of time summing up numbers that are not known to work. (For example, if 1 + 2 is already too large, it makes no sense to try 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ..., too.)

So I wrote an improved version. He does not use bit magic, he does everything manually. The downside is that it requires sorting the input values ​​(use rsort ). But this should not 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; } 

Modified version of oezis testing program (see end):

 possibilities: 540 took: 3.0897309780121 

Thus, it took only 3.1 seconds to execute, while the oezis code ran 65 seconds on my machine (yes, my machine is very slow). It is over 20 times faster!

Also, you may notice that my code found 540 instead of 338 possibilities. This is because I configured the testing program to use integers instead of floats. Direct comparisons with floating point are rarely correct, this is a great example: you sometimes get 59.959999999999 instead of 59.96 , and therefore a match will not be considered. So, if I run oezis code with integers, it will also find 540 possibilities;)

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 to add a new answer, but this is a complete new solution to solve all the problems of life, the 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 do not use the third parameter, it returns the best (with the least number of numbers) solution in the form of an array (whith keys of the input array) - if you set the third parameter to true , ALL (for testing I used the same numbers as zaf in your message - in this case, 338 solutions found in ~ 10 seconds on my machine).

EDIT: if you get everything, you will get results sorted by what is “best” - without it, you will only get the first solution found (which is not necessarily the best).

EDIT2: in order to satisfy the desire for some explanation, I commented on the main parts of the code. if anyone needs more explanation please ask

Answer 3

 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 takes less time to complete.

Answer 4

The following method will give you an answer ... almost all the time. Increase the iteration variable to your liking.

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

Probably an inefficient but simple backtracking solution

 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 6

Not knowing whether this is a homework task or not, I can give you some pseudo-code as a hint for a possible solution, we note that the solution is not very efficient, more demonstration.

Hint:

Compare each field value with the entire field value and each iteration test, if their sum is TOTAL_AMOUNT .

Pseudocode:

 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:

It seems that you have the Subset Sum Problem specified in the Wiki link is a pseudo-code for an algorithm that can help you point in the right direction.

Answer 7

I do not think the answer is not as simple as Nick mentioned. let you have the following numbers:

 1 2 3 6 8 

looking for quantity 10

Niks solution will do this (if I understand correctly):

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

now he will delete a large number and will again begin to take a new maximum

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

... etc., where the ideal answer is simply be 8+2 = 10 ... I think that the only solution is trying all kinds of combinations of numbers and stop if the amputation you find is found (or really calculate everything if there are different solutions and save which one used the smallest numbers).

EDIT: the real calculation of all possible combinations of 21 numbers will be completed in real, real, real calculations - therefore there should be any “smart” solution for adding numbers in a special order (for example, one in niks post - with some improvements, maybe this will lead us to a reliable solution)