使用整数列表，我应该使用哪些算法查找给定总数的最接近的解决方案？

Question

我的问题是：

让我们说我有一个任意整数列表A [2013,54,3,32 1,23 ...]

找到哪些我应该添加的最佳策略是什么，以便与给定的数字相等或最接近给定号码？

显然，总有蛮力方法，但我很兴趣知道是否有更优化的强制性。

Answer 1

将行李包装到汽车时，首先将最大的物品放在围绕它们周围的较小物品。通过类比，您问题的启发式方法是从您的集合的成员开始，同时仍然小于目标。然后重复对您当前总数和目标之间的差异的过程，等等。这被称为贪婪算法。

例如，如果您的设置是 $ \ {2,3,5,8,13,21,34 \} $ 并且您的目标是 $ 32 $ ，从 $ 21 $ （比 $ 32 $ ），然后添加 $ 8 $ （因为这是大于 $ 32-21= 11 $ < / span>），然后添加 $ 3 $ 。

贪婪算法快速简单，但并不总是为您提供最佳解决方案。例如，如果您的设置是 $ \ {1,5,23,26 \} $ 并且您的目标是 $ 30 $ 然后贪婪算法给出 $ 26 + 1= 27 $ ，而最佳解决方案是 $ 23 + 5 + 1= 29 $ 。

Answer 2

问题是NP-Cleante，但多项式在给定数量的值中，多项式程度相当低。如果所涉及的数字很大，这才很难。

从最小到最大并添加直到没有数字契合不是很聪明，因为它可能是一个不适合的相当大的数字，并且你不会接近所需的总和。更好地排序从最大到最小，并先添加最大的数字。

现在，如果您有一个sum 关闭 to s，则可以尝试提高此问题。例如，如果您的总和太小了117，但最小的未使用的项目是317，如果您的列表中有项目x，则尝试，并且在列表中的项目y，其中y大约200多于x - 将x对y互换，添加大小317。即使是简单的算法也可能会找到良好的改进。

一种完全不同的方法：让所需的总和是s，具有非常大的s（如多万亿）。然后，您可以选择左右1,000,000，乘以（s'/ s）的所有数字乘以（s'/ s），查找含量接近1,000,000的项目，然后选择原始项目。尝试几个近1,000,000的总和。

Answer 3

感谢@Yuval的评论，我导致了背包问题，这正是我正在寻找的。

虽然我不了解Wikipedia中对该NP完全问题的大部分解决方案，但我想到了快速但完全不可靠的方法：

只需对最小到最大的可用整数列表并开始添加它们，直到满足所需的条件。

我认为，如果整数集合的两个成员之间的所有差异都不会变化，那么这种方法可能会提供最佳和唯一的解决方案。