给定一个目标总和和一组整数，找到与该目标相加的最接近的数字子集 [英] Given a target sum and a set of integers, find the closest subset of numbers that add to that target

问题描述

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

I have a set of integers M and a target sum k. I want to find the subset of M that when added together is the closest to k without going over.

例如:

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 个元素.

I have the additional constraint that the subset can contain at most 4 elements.

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

In my application, the size of |M| can be large (on the order of thousands of elements). If it is not possible to find the optimal answer in a reasonable time, I am interested in solutions that at least give a "good" answer.

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

Right now I am solving this problem by generating 10,000 random subsets and selecting the closest one, which works better than one might expect but is slow. I'm not sure how far from optimal this actually is, but any insight on that would be interesting to me as well.

推荐答案

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

Since you have a limit on the number of items that you can pick, you can do it with a reasonably straightforward algorithm.

该算法以代"生成可能的总和.一代的每个元素都包含一个表示总和的数字，以及用于构建该总和的 M 中索引的 N 元组.

The algorithm produces the possible sums in "generations". Each element of a generation consists of a number representing the sum, and a N-tuple of indexes in M that were used to build that sum.

零代为空；X+1 生成是遍历生成 X 生成，并将 M 的元素添加到该生成的每个值，并记录它们的总和为下一代X+1.

Generation zero is empty; generation X+1 is produced by walking the generation X, and adding the elements of M to each value of that generation, and recording their sum for the next generation X+1.

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

Before computing the sum, check its N-tuple for the presence of the index of the number that you are about to add. If it's there, skip the number. Next, check the sum: if it is already present among the X+1 sums, ignore it; otherwise, record the new sum, along with the new N-tuple of indexes (append the index of the number that you added to the N-tuple from the generation X).

这是您的输入的工作方式:

Here is how this would work for your inputs:

0代:空

第一代:

 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}

第三代:

 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 的数字.

You can now search through the four generations for a number that is closest to your target number k.

这篇关于给定一个目标总和和一组整数，找到与该目标相加的最接近的数字子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！