c# - 计算最接近给定数字的数字之和

Question

我想找出在 C# 中执行此操作的最佳方法是什么：我有一组让我们说 20 个数字，然后是一个额外的变量。我想得到最接近给定变量的数字的总和。可以说，我有 1.1、1.5、1.7、1.9、2.2、3.1、3.2、1,5、4.5、4.1。然后附加变量的值为5。我想得到数组中最接近给定数字的一些数字的总和，一旦我得到那个数字，就从列表中删除这些数字并将它们添加到一个新的数组。欢迎每条评论。谢谢

Answer 1

您正在描述Subset Sum Problem的优化问题。

问题是NP-Complete，因此没有已知的多项式解决方案。

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

伪代码应该是这样的：

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