algorithm - 查找可被给定数字整除的数组元素的最大总和

Question

这是一道编程题。

题目如下:

将给出一个数字数组以及我们要除以的数字 k。我们必须从该数组中选择元素，使得这些元素的总和可以被 k 整除。这些元素的总和应尽可能大。

输入:

第一行n，表示元素个数。

在下一行给出了 n 个数字。

在下一行给出了 k，我们必须除以它。

输出:

通过从该数组 s.t. 中选择元素来获得尽可能大的总和。总和可以被 k 整除。

示例输入:

5 
1 6 2 9 5
8

示例输出:

16

请注意，16 可以通过不止一种数字组合获得，但我们这里只关心最大和。

我提出的解决方案:

我遍历数组并在数组 b 中维护给定输入数组的累积和，例如:

b=[1 7 9 18 23]

然后将数组b中的数字乘以k取模并将其存储到

c=[1 7 1 2 7]

现在 c 中具有相同值的数字，即索引 0 和索引 2；索引 1 和索引 4。现在我有了所有的解决方案，答案是

max(b[2]-b[0],b[4]-b[1])

如果三个索引在 c 中具有相同的值，即在这种情况下

c=[1 2 3 1 1 2]

答案是

max(b[4]-b[0],b[5]-b[1])

基本上是用最右边出现的数字减去最左边出现的数字。

我的解决方案仅在有连续元素 s.t 时才有效。元素之和可以被 k 整除。期待正确解决方案的描述

Answer 1

我认为您的解决方案不正确，因为您只考虑连续的数字。例如，如果输入是

4
1 6 2 9
8

答案仍然是 16 (=1+6+9)。我不确定您的解决方案是否可以给出这个答案。

---

要有效解决此问题，请尝试动态规划。我会省略细节，但会指出要点。

假设数字在数组 a[i] 中，其中 i 是从 1 到 n。

令 f(i,j) 表示从 a[1] 到 a[i] 中选择数字可以获得的最大总和>(即 a[1]、a[2]、...、a[i])并且求和模 k 是 j.

考虑f(i,j)，显然我们有两个选择:(1)在求和中包含a[i]； (2) 不包含a[i]。因此 f(i,j) = max{ f(i-1,x) + a[i], f(i-1,j) } 其中 x + a[i] == j (mod k)。对于所有 j

，边界是 f(0,j) = 0

---

为了实现这个算法，基本框架如下。

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i][j] = max(f[i-1][x], f[i-1][j]);
  }

为了节省内存，也可以使用大小为[2][k]的数组代替[n][k]:

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i%2][j] = max(f[(i-1)%2][x], f[(i-1)%2][j]);
  }

您还可以使用 i&1(和 (i-1)&1)来加速 2 的模运算。

---

关于动态规划的进一步引用:

• TopCoder 教程:Dynamic Programming: From novice to advanced
• 动态编程 - 一种计算工具，作者是 Art Lew 教授和 Holger Mauch 博士
• 动态编程 - 基础和原则，作者 Moshe Sniedovich