Re: Number Comparisons

Here's a PHP function that solves Michael's problem, and it should be pretty efficient if the numbers involved are small. The function takes two arguments: an integer maximum, and an array of integers. It returns an array containing a subset of those integers with the highest possible sum that is less than or equal to the maximum. (There may be more than one subset that adds up to that highest sum, and this function will only return one of them.) See my earlier note below for the algorithm. function maximum_subset_sum ($max, $candidate_array) { $working_array = array(); while ($next = each($candidate_array)) { $candidate = $next['value']; $sums_to_date = array_keys($working_array); while ($marked_sum = each($sums_to_date)) { $known_sum = $marked_sum['value']; $possibly_new = $known_sum + $candidate; if(($possibly_new <= $max) && !IsSet($working_array[$possibly_new])){ $working_array[$possibly_new] = $candidate; } } if(($candidate <= $max) && !IsSet($working_array[$candidate])){ $working_array[$candidate] = $candidate; } } $max_sum = max(array_keys($working_array)); $return_array = array($working_array[$max_sum]); while ($max_sum != $working_array[$max_sum]) { $max_sum = $max_sum - $working_array[$max_sum]; array_push($return_array, $working_array[$max_sum]); } return($return_array); } // example use $best_sum = maximum_subset_sum(40, array(39,23,19,14,9,5,3,2,1)); print("Largest sum is " . array_pop($best_sum)); while ($value = array_pop($best_sum)) { print(" + $value"); } // will print "Best sum is 23 + 14 + 3" On Mon, 2 Oct 2000 20:13:20 -0700 (PDT), Tim Converse wrote: > This is a hard one -- it's the "subset sum" problem, which is a version of > the "knapsack problem". It is known to be NP-hard, which means that if need > to solve it exactly, for arbitrary integers, then there's no known solution > which is substantially faster than trying all the different possible > combinations. > > If you can guarantee a pretty small, fixed, maximum size for your target > number, then the problem becomes easier. Check out the following page, and > search for "subset sum": > > http://www.tcs.mu-luebeck.de/AlgoDesignMan/BOOK/BOOK4/NODE145.HTM#knapsack > > The basic idea is to use an array with as many potential slots as the size > of the target number. You then make a pass over the array for each number > in your set, and on each pass you mark every slot number that has now become > a possible sum. So that you can reconstruct the sum later, we use the > number that made the sum possible as the marker. > > For example: > > First pass (using 20): > > $my_array[20] = 20; // the sum of 20 is .. 20 > > Second pass (using 9): > > $my_array[9] = 9; > $my_array[29] = 9; // the 20 slot plus the current 9 > > Third pass (using 7): > > $my_array[7] = 7; > $my_array[16] = 7; > $my_array[27] = 7; > $my_array[36] = 7; // the 29 slot plus seven (20 + 9 + 7) > (etc.) > > When you've used up all the numbers, check the array for the highest marked > slot (having already ruled out slots above the target number). That slot > number is the best you can do. Now to find the sum that made it, just > "unwind" from the top slot. (I.E., to find how you filled the 36th slot, > subtract the 7 you stored there to find the 29th slot, etc ...). > > If there's any interest, I'd be happy to code this in PHP and post it. > > --tim > > On Mon, 2 Oct 2000 22:28:04 +1000, Real GM Webmaster wrote: > > > What I need to do is take a number, say 40, and then have a varying > number of other integers that I need to find the best fit into the original > number. There could be four, give, or 25 numbers that could fit. > > > > For example, using 40 as the basis. > > > > Just say on the flip side I have 20, 9, 7, 5, and 2. > > > > I need to find the sum of these numbers that will end up closest to 40. > In this case the numbers that would be returned would be 20, 9, 7 and 2, > which equals 38.. 5 would be left over. Any other sum would either push me > over the 40 mark or would fall short of the 38. > > > > Any idea on how to do this. Remember, that the number of numbers that > will be compared is not static. > > > > Please help me, because I am completely stuck and this is vital to the > accuracy of our site. > > > > Thank you in advance, > > > > Michael. ------------- How can you support PHP *and* me at the same time? Order the PHP 4 Bible using http://www.php.net/books.php. :) _______________________________________________________ Say Bye to Slow Internet! http://www.home.com/xinbox/signup.html