我想了解一下什么是做到这一点在C＃中的最佳方式： 我有一个数组可以说20号，然后多了一个额外的变量。 我想获得的最靠近给定的变量的数目的总和。 比方说，我有1.1，1.5，1.7，1.9，2.2，3.1，3.2，1.5，4.5，4.1。然后将附加的变量具有值5。 我想这将是最接近给定的数字数组中的一些数字的总和，有一次我会得到这个数字，从列表中删除这些数据，并将其添加到一个新的数组。 每一个评论是值得欢迎的。 谢谢

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

推荐答案

您所描述的优化问题，对于的子集和问题

You are describing the optimization problem for Subset Sum Problem.

问题是 NP完全的，所以没有已知多项式溶液到它

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

然而，由于输入是相当小的规模 - 一个指数解决方案的检查所有的子集是可行的，因为只有2 ^ 20〜= 1000000（多一点，实际上，但是足够接近估计运行时间）

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)

伪code应该是这样的：

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