algorithm - 从列表中查找一组特定的数字

Question

我正在做这个项目，用户输入一个数字列表。我把这些数字放在一个数组中。我需要找到一组给定长度的数字，其总和可以被 5 整除。

例如，如果列表为 9768014，所需长度为 6，则输出为 987641。

我需要什么算法来找到那组数字？

Answer 1

你可以用动态规划来解决这个问题。设 f(n,m,k) 是索引子集 {1,2,....,n} 中数字的 1 和 n 之间的最大索引，它给出使用 m 个数字的 k mod 5 之和。 (有可能 f(n,m,k) = None)。如果您知道所有 N <= n + 1 和 M < m 的 f(N,M,k) 的值，则可以计算 f(n+1,m,k) 和 f(n,m+1,k)也适用于所有 N <= n 和 M < m + 1 以及 N=n,M=m 和所有 k = 0,1,2,3,4。如果您发现 f(n,m,0) 有一个解决方案，其中 m 是您想要使用的数字数量，那么您就完成了。此外，您不必为任何大于您想要使用的数字数量的 M 计算 f(N,M,k)。总复杂度为 O(n*m)，其中 n 是数字的总数，m 是您要达到的子集的大小。