algorithm - 这可能吗？总和的最后几位等于另一个数字

Question

我有一个 n 位数字和一个数字列表，其中任何数字都可以使用任意次数。

从列表中获取数字，我怎么知道可以生成一个总和，使得总和的最后 n 位数字是第 n 位数字？

注意:总和有一些初始值，它不是零。

编辑 - 如果存在解决方案，我需要找到添加的数字的最小数量以获得一个数字，以便它具有最后 4 位数字作为给定数字。这很容易用 DP(最小硬币找零问题)解决。

例如，如果n=4，

Given number  = 1212
Initial value = 5234
List = [1023, 101, 1]
A solution exists: 21212 = 5234 + 1023*15 + 101*6 + 1*27

Answer 1

很容易找到反例(见评论)。

现在，这里的解决方案是动态编程方法:

所有算术都是模 10^n。对于 0 - 10^n-1 范围内的每个值，您需要一个标志是否找到它，并且您需要一个队列来处理要处理的元素。

1. 将初始值推送到待处理列表。
2. 从待处理列表中获取一个元素。如果为空，则完成。没有解决方案。
3. 尝试将每个数字分别添加到此数字。如果已经找到，则无需执行任何操作。如果找到总和，你就完成了，有一个解决方案。如果没有，将其标记为已找到并将其推送到队列。
4. 转到 2

如果您存储达到某个数字的方式，则可以重建实际的解决方案。您只需从 sum 返回，直到达到初始值。