algorithm - 将一组数字的元素相加到给定的数字

Question

我一直在努力提出一种算法来解决这个问题。假设我有一组数字{1, 2, 5}，并且这个集合中的每个元素都是无限供应的，我给了另一个数字 6，然后要求确定可以将元素相加得到数字 6 的方法的数量。为了说明目的，我做了这个

1 + 1 + 1 + 1 + 1 + 1 = 6

1 + 1 + 2 + 2 = 6

2 + 2 + 2 = 6

1 + 5 = 6

1 + 1 + 1 + 1 + 2 = 6

所以在这种情况下，程序将输出 5 作为路数。再次假设您要找到 4 的总和，

1 + 1 + 1 + 1 = 4

2 + 2 = 4

1 + 1 + 2 = 4

在这种情况下，算法将输出 3 作为路数

标签： algorithm

Answer 1

这类似于子集总和问题。我相信你必须使用分支和绑定方法或回溯方法。

1）创建一个包含所有可能情况的状态空间树。

                        0
                    /   |   \
                   1    2     5
                 / | \
                1  2  5 ........

2）继续该过程，直到深度优先方式的节点总和大于或等于您想要的数量。

3) 数数。满足您的条件的完整分支。

可以在此处找到类似问题的 python 实现。