calculate sum of numbers closest to a given number

问题:

I want to find out what is the best way to do this in C#: I have a array of lets say 20 numbers, and then one more additional variable. I want to get the sum of the numbers which is closest to the given variable. Lets say, I have 1.1, 1.5, 1.7, 1.9, 2.2, 3.1, 3.2, 1,5, 4.5, 4.1. And then the additional variable has value of 5. I want to get the sum of some numbers in the array which will be closest to the given number, and once I'll get that number, remove those numbers from the list and add them to a new array. Every comment is welcomed. Thanks

回答1:

You are describing the optimization problem for Subset Sum Problem.

The problem is NP-Complete, so there is no known polynomial solution to it.

However, since the input is fairly small scale - an exponential solution of checking all subsets is feasible, since there are only 2^20 ~= 1000000 (a bit more, actually, but close enough for estimating run time)

Pseudo code should be something like:

getClosestSum(list,sum,number):
  if (list is empty):
      return sum
  candidate1 <- getClosest(list[1:],sum,number)
  candidate2 <- getClosest(list[1:],sum+list[0],number)
  if (abs(number-candidate1) < abs(number-candidate2)):
      return candidate1
  else:
      return candidate2