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