由于您可以选择的物品数量有限制,因此可以使用相当简单的算法来做到这一点。
该算法以“世代”产生可能的总和。一代中的每个元素都由代表总和的数字以及其中的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}
第三代:
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
。