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

Question

这是一个编程问题.

问题如下:

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

输入:

在第一行n上,表示元素的数量.

在下一行,给出了n个数字.

在下一行,我们必须划分k.

输出:

通过从该数组st sum中选择元素,尽可能最大的和可被k整除.

样本输入:

5 
1 6 2 9 5
8

样本输出:

16

注意16可以通过多个数字组合获得,但我们这里只关注最大总和.

我建议的解决方案:

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

b=[1 7 9 18 23]

并将数组中的数字mod乘以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])

基本上减去最右边出现的那个数字的最左边的出现.

我的解决方案只有在有连续元素时才有效.元素之和可以被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).边界f(0,j) = 0适合所有人j

为了实现该算法,基本骨架如下.

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教程:动态编程:从新手到高级
• 动态编程 - Art Lew教授和Holger Mauch博士的计算工具
• 动态编程 - Moshe Sniedovich的基础和原理