From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math Subject: Re: Combination Selection Problem Date: 18 Dec 1997 17:38:32 GMT In article , Jeff Lewis wrote: >Is there a method (other than "brute force") for solving the following >problem? (By brute force I mean checking every one of the billions of >combinations) >Say I have 15 random numbers between 50.0 & 100.0 >How can I select the BEST POSSIBLE combination of numbers out of the >15 to get as close as possible to a total of, say, 500.0? This is a type of "subset-sum" problem. The corresponding decision problem (in an integer formulation) is NP-complete, if I recall correctly. So there is no very efficient method known. But you can get an approximate answer (probably very close to optimum, if not the BEST) by dynamical programming. Take some positive integer N: you will be doing approximately 15 N steps, so don't make it too huge. On the other hand, your answer will be no more than 7500/N away from the correct answer. Multiply each number by N/500 and round to the nearest integer. Now you have positive integers x_i, i = 1 .. 15, and you want to select a subset whose sum is as close as possible to N. Let V(j,x) be the minimum of |N - x - S| where S is the sum of a subset of { x_i , i = j .. 15 }. Thus what you want is V(1,0). Work backwards from V(15,x) = min(|N-x|, |N-x-x_15), using V(i,x) = min(V(i+1,x), V(i+1,x+x_i)) to calculate all V(i,x) for i = 2 .. 15 and x = 0 .. N-1 (of course V(i,x) = x - N for x >= N). Then work forwards to get the subset, including x_i if V(i, total_so_far) = V(i+1, total_so_far + x_i). Robert Israel israel@math.ubc.ca Department of Mathematics (604) 822-3629 University of British Columbia fax 822-6074 Vancouver, BC, Canada V6T 1Z2