Thursday 15 September 2011

algorithm - Sum of a subset of numbers -


I have a number 'n' and a table of numbers. I want to select four numbers in the table, and the number of those four will be the closest possible match. Given the length of the table 'L', the number of coincidences is (6 * L + 11 * L ^ 2 + 6 * L ^ 3 + L ^ 4) / 24

East. I have the variable

  n = 100   

and the set of numbers

  t = {86, 23, 19, 8, 42, 12, 49}   

Given this list, the closest combination of four to n is 49 + 23 + 19 + 8 = 99.

> What is the optimal way to do this with the least possible number of calculations?

It looks like a NP is known to meet which 'subset amount ' (see: There is a variation of the problem), so unfortunately, most probably there will be no clever algorithm which will run in the worst case of the number of items at any speed.

If there are not many things to check (about 10 or so) then you may try the first search sorting branches as soon as possible.

If there are too many items to investigate the optimum solution, you can try to make better guesswork better.

No comments:

Post a Comment