给定目标总和和一组整数,找到添加到该目标的最接近的数字子集

Question

我有一组整数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个随机子集并选择最接近的子集来解决这个问题,这个子集的效果比预期的要好但是很慢.我不确定这实际上有多远,但任何有关这方面的见解对我来说都很有趣.

Answer 1

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

该算法在"世代"中产生可能的总和.一代中的每个元素由表示总和的数字组成,并且其中的N元组M用于构建该总和.

第零代是空的; 生成X+1是通过遍历生成X,并将元素添加M到该代的每个值,并记录它们的总和用于下一代X+1.

在计算总和之前,检查其N元组是否存在您要添加的数字的索引.如果它在那里,请跳过该号码.接下来,检查总和:如果总和中已经存在X+1,则忽略它; 否则,记录新的总和,以及新的N元组索引(追加你从一代中添加到N元组的数字的索引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.