Re: Number Comparisons

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: > Hi, > > I have a problem that has had be scratching my head for the last three weeks. > > 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. > _______________________________________________________ Say Bye to Slow Internet! http://www.home.com/xinbox/signup.html