我有一组整数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个随机子集并选择最接近的子集来解决此问题，该子集的工作效果比预期的要好，但速度较慢。我不确定这实际上离最佳距离有多远，但是对此的任何见解对我来说也很有趣。
由于您可以选择的物品数量有限制，因此可以使用相当简单的算法来做到这一点。
该算法以“世代”产生可能的总和。一代中的每个元素都由代表总和的数字以及其中的N个索引元组成M总和。
M
零代为空；一代X+1是通过遍历一代X并将其元素M与该一代的每个值相加，并记录其下一代的总和而产生的X+1。
X+1
X
在计算总和之前，请检查其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}
第三代：
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}
第四代：
14 - {0, 1, 2, 3} 23 - {0, 1, 2, 4} 25 - {0, 2, 3, 4} 27 - {1, 2, 3, 4}
现在，您可以搜索四代，找到最接近您的目标编号的数字k。
k
