定一个目标之和是一个整数集，找到号码的该添加到该目标最接近的子集 [英] 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.

现在，我通过生成万随机的子集，选择最接近的一个，这作品比人们所预料的好，但速度很慢解决这个问题。我不知道怎么很不理想这实际上是，但任何有识之士将是有趣的，我也是如此。

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.

该算法产生可能的款项，代。一代的每个元素包含了一些重presenting的总和，而在 M A 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元组，你将要添加的号码指数的presence。如果它的存在，跳过的次数。接下来，检查和：如果是已经$之间的点$ psent X + 1 款项，忽略它;否则，记录新的总和，随着新的N-元组索引（追加您从一代加入到N-元组的数目的指数 X ）。

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代：

 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}
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屋！