1

我有一个 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
4

2 回答 2

1

很容易找到一个反例（见评论）。

现在，对于解决方案，这是一种动态编程方法：

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

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

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

于 2013-06-07T02:55:01.307 回答
0

如果列表中数字的最大公因数是一个以 10 n为模的单位（即，不能被 2 或 5 整除），则您可以通过选择其他给定值来解决问题：使用扩展欧几里得算法找到求和为 gcf 的列表的线性组合，找到 gcf 模 10 n的乘法逆，并乘以给定值和初始值之间的差。

如果列表中数字的 gcf 能被 2 或 5 整除（即不是一个单位）并且给定值与初始值的差值也能被 2 或 5 整除，则将列表中的数字除以将它们全部除以 2 和 5 的最大幂的差异。如果您最终得到的 gcf 是一个单元，则有一个解决方案，您可以通过上述过程找到它。否则没有解决办法。

例如，给定 16 和初始值 5，以及数字列表 [3]。

列表中数字的 gcf 是 3，这是一个单位。它的反模 100 是 67 (3×67 = 201)。

乘以给定数字和初始值 16-5 = 11 之间的差值，我们得到 3 的因数 67*11 = 737。因为我们正在使用模 100，所以它与 37 相同。

检查结果：5 + 37×3 = 16。是的，这行得通。

于 2013-06-07T07:42:14.167 回答