取最好的一组数字求和的算法

Question

我试图找到算法来将表格/列表中的少量资金加起来等于或可能最接近（但不大于）ceratin 数。

让我通过例子来解释它。我有一个数字列表：
{ 1.23 ; 3.45 ; 20.11 ; 100.13 ; 200.08 }

我想得到的数字是 123.69

所以应该采取 { 3.45 ; 20.11 ; 100.13 } = 123.69

如果数量是122它不应该采取相同的，但{ 20.11 ; 100.13 ; 1.23 } = 121.47

有什么想法如何写这样的东西吗？

Answer 1

这是子集和问题的一种变体，使用 DP 可以很容易地解决仅涉及整数的经典问题，并且可以在 StackOverflow 的许多线程中找到，例如这个。

但是，您的问题有一个小调整，使其与经典的整数子集和问题略有不同 - 您正在处理的值不一定是整数，它们也有一个十进制值。

在您的情况下，十进制值似乎在“点之后”最多为 2 位数字。这意味着，您可以通过简单地将数组中的所有值乘以 100 并搜索100*x而不是 ，轻松地将您的问题转换为经典的整数子集和问题x。
在您的示例中 - 您需要在整数值数组中查找 12,369 {123, 345, 2011, 10013, 20008}。

附件 1： 解决整数的 SubsetSum 问题：
这是使用Dynamic Programming完成的，其中 DP 的递归公式是：

f(x,0) = FALSE if x<0
f(0,0) = TRUE
f(x,i) = f(x,i-1) OR f(x-arr[i], i-1)

通过计算上述自下而上，您将获得一个大小矩阵(W*100+1) x (n+1)（其中W是您请求的总和，n是数组中的元素数）。

通过在完成后搜索包含该值的最后一行中的列true- 您找到了与您的数字相符的“最佳”可能总和。

附件 2：查找数字的实际子集。
到目前为止，您已经找到了您能得到的最好金额，但还没有找到最好的数字。为此，您需要使用您的矩阵（您之前计算过的），并重播您为生成此总和所做的步骤。这在此线程中针对类似问题进行了解释，简而言之，它是通过以下方式完成的：

line <- BEST //best solution found
i <- n
while (i> 0):
  if table[line-array[i]][i-1] == TRUE:
      the element 'i' is in the set
      i <- i-1
      line <- line-array[i]
  else:
      i <- i-1 

注意：如果这太复杂，并且数组的大小相当小，或者“点后小数点后两位”限制不正确 - 您几乎必须使用指数解决方案 - 蛮力，这创造了所有可能子集，并从中选出最好的。在这种情况下没有（已知的）有效解决方案，因为这个问题已知是NP-Hard

tl;dr： 将所有值乘以 100，然后使用现有的整数子集和问题算法找到最佳拟合。