19

我有一组整数 M 和一个目标总和 k。我想找到 M 的子集，当它加在一起时最接近 k 而不会超过。

例如：

M = {1, 3, 5, 5, 14}

k = 12

answer = {1, 5, 5}

because 1 + 5 + 5 = 11 and there is no way to make 12.

我有一个额外的约束，即子集最多可以包含 4 个元素。

在我的应用程序中，|M| 的大小 可以很大（大约有数千个元素）。如果无法在合理的时间内找到最佳答案，我会对至少给出“好”答案的解决方案感兴趣。

现在我正在通过生成 10,000 个随机子集并选择最接近的子集来解决这个问题，这比人们预期的要好，但速度很慢。我不确定这实际上离最优还有多远，但任何对此的见解对我来说也会很有趣。

4

3 回答 3

14

由于您可以选择的项目数量有限，因此您可以使用相当简单的算法来完成。

该算法产生“世代”中的可能总和。一代的每个元素都由一个表示总和的数字和一个M用于构建该总和的索引的 N 元组组成。

零代为空；一代X+1是通过遍历一代产生的X，并将该代的M每个值相加，并为下一代记录它们的总和X+1。

在计算总和之前，检查它的 N 元组是否存在您要添加的数字的索引。如果它在那里，请跳过该数字。接下来，检查总和：如果总和中已经存在X+1，则忽略它；否则，记录新的总和以及新的 N 元组索引（将您添加到 N 元组中的数字的索引从 generation 附加X）。

以下是这将如何为您的输入工作：

第 0 代：空

第 1 代：

 1 - {0}
 3 - {1}
 5 - {2}
14 - {4}

第 2 代：

 4 - {0, 1}
 6 - {0, 2}
 8 - {1, 2}
10 - {2, 3}
15 - {0, 4}
17 - {1, 4}
19 - {2, 4}

第 3 代：

 9 - {0, 1, 2}
11 - {0, 2, 3}
13 - {1, 2, 3}
18 - {0, 1, 4}
20 - {0, 2, 4}
22 - {1, 2, 4}
24 - {2, 3, 4}

第 4 代：

14 - {0, 1, 2, 3}
23 - {0, 1, 2, 4}
25 - {0, 2, 3, 4}
27 - {1, 2, 3, 4}

您现在可以在四代中搜索最接近您的目标号码的号码k。

于 2013-10-24T17:09:34.700 回答
2

如果目标总和 k 不是太大，请查看http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution - 您可以使用它创建一个位图，告诉您可以使用您的子集生成哪些数字。然后只需在位图中选择最接近 k 的可能数字。

于 2013-10-24T17:14:25.007 回答
2

将问题拆分为 4 个部分：

  • 总和正好包含 1 个元素

    只需循环并找到不大于目标的最大值。

  • 恰好包含 2 个元素的总和

    使用双 for 循环找到不大于目标的最大总和。

  • Sum 正好包含 3 个元素（类似于3SUM）

    对元素进行排序

    使用双 for 循环并对目标进行二分搜索减去两个值，寻找较小的值以找到不大于目标的最大总和。

  • 恰好包含 4 个元素的总和

    对元素进行排序（已经完成）

    使用双 for 循环生成 2 个元素的所有总和。

    现在，对于每个这样的总和，对目标的总和进行二进制搜索，寻找较小的值，直到我们找到一个不包含该总和的任何一个值的值。

    有关使用此方法解决类似问题（确切总和）的代码，请参阅此内容。

平均案例运行时间 (?) = O(n + n^2 + n^2 log n + n^2 log n) = O(n^2 log n).

确定最后一个问题的运行时间有点困难，它可能O(n^4 log n)与最坏的情况一样糟糕，因为您可能最终会在找到适合的问题之前查看其中的大部分，但这应该很少发生，并且在同样的运行，一些应该花费更少的时间，因此整体运行时间可能会更少。

于 2013-10-24T17:17:19.013 回答