使用一组给定数字生成增量数字直到固定数字的算法

Question

我们有一个要求，我们希望使用给定的一组数字生成 增量数字 直到目标数字。（给定的数字集可能会有所不同，并且该算法需要适用于任何数字集。尽管实际上我们期望该集最多包含 15 个数字。）

假设：假设给定集合中的所有数字都是整数。

递增数字我的意思是通过将给定数字集的倍数相加得到所有可能的数字。

例如假设我们有一个集合 {12, 13, 17} 并且目标数字是 50。那么增量数字是 {0, 12, 13, 17, 24, 25, 26, 29, 30, 34, 36, 37 , 38, 39, 41, 42, 43, 46, 47, 48, 49, 50}

(以上增量数说明：

0 = (12 * 0) + (13 * 0) + (17 * 0)

12 = (12 * 1) + (13 * 0) + (17 * 0)

13 = (12 * 0) + (13 * 1) + (17 * 0)

17 = (12 * 0) + (13 * 0) + (17 * 1)

24 = (12 * 2) + (13 * 0) + (17 * 0)

25 = (12 * 1) + (13 * 1) + (17 * 0)

26 = (12 * 0) + (13 * 2) + (17 * 0)

29 = (12 * 1) + (13 * 0) + (17 * 1)

30 = (12 * 0) + (13 * 1) + (17 * 1)

34 = (12 * 0) + (13 * 0) + (17 * 2)

36 = (12 * 3) + (13 * 0) + (17 * 0)

37 = (12 * 2) + (13 * 1) + (17 * 0)

38 = (12 * 1) + (13 * 2) + (17 * 0)

39 = (12 * 0) + (13 * 3) + (17 * 0)

41 = (12 * 2) + (13 * 0) + (17 * 1)

42 = (12 * 1) + (13 * 1) + (17 * 1)

43 = (12 * 0) + (13 * 2) + (17 * 1)

46 = (12 * 1) + (13 * 0) + (17 * 2)

47 = (12 * 0) + (13 * 1) + (17 * 2)

48 = (12 * 4) + (13 * 0) + (17 * 0)

49 = (12 * 3) + (13 * 1) + (17 * 0)

50 = (12 * 2) + (13 * 2) + (17 * 0)

)

有人可以帮我优化解决方案吗？

Answer 1

这里很难比蛮力方法做得更好。您可以丢弃可被列表中的另一个数字整除的任何数字。然后，您可以使用以下算法：

lst = [12,13,17]
target = 50
sums = {0}
for i in lst:
    new_sums = set()
    for j in sums:
        x = j + i
        while x <= target and x not in new_sums:
            new_sums.add(x)
            x += i 
    
    sums = sums.union(new_sums)

print(sums)
# {0, 12, 13, 17, 24, 25, 26, 29, 30, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 50}

使用一组给定数字生成增量数字直到固定数字的算法

Algorithm to generate incremental numbers up to a fixed number using a set of given numbers

algorithm

math

computer-science

numbers