11

它来自一个编程问题。

问题如下：

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

输入：

在第一行 n，表示元素的数量。

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

在下一行 k 给出了我们必须划分的。

输出：

通过从该数组中选择元素来尽可能大的总和 st 总和可被 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])

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

我的解决方案仅适用于存在连续元素 st 元素之和可被 k 整除的情况。期待正确解决方案的描述

4

5 回答 5

14

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

4
1 6 2 9
8

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

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

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

让表示通过从(ie )f(i,j)中选择数字可以获得的最大总和，并且总和模为。a[1]a[i]a[1], a[2], ..., a[i]kj

考虑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(and (i-1)&1) 来加速2.

关于动态规划的更多参考资料：

  • TopCoder 教程：动态编程：从新手到高级
  • 动态规划 - Art Lew 教授和 Holger Mauch 博士的计算工具
  • 动态编程 - Moshe Sniedovich 的基础和原理
于 2012-11-22T11:53:29.137 回答
4

听起来像是子集总和的变体：您想要总和可被 整除的最大子集k。

让dp[i] = largest sum obtainable that gives remainder i modulo k. 但是，为了避免两次使用相同的元素，我们必须使用两个数组，因为模数：包含dp( ) 的当前值的数组和包含(dp2)dp1的先前值的数组。dp我们有：

a = original array
dp1[*] = dp2[*] = 0 
for i = 1 to n do
  for j = k - 1 down to 0 do
    dp1[j] = max(dp1[j], dp2[(j - a[i]) mod k] + a[i])

  copy dp1 to dp2: on the next iteration, the current array will must become the
  previous one (*)

(*)请注意，如果执行时间非常重要，您不必进行任何复制。您可以使用数组dp[2, k]并交替使用它的行：在奇数迭代中计算从dp[0, _]到dp[1, _]，在偶数迭代中反之。

答案将在dp1[0, 0]或中dp2[0, 0]。使用的内存是O(n + k)和时间复杂度O(n * k)。

注意：在实现这一点时，您可能需要以这种方式进行模运算以避免负值：((j - a[i]) mod k + k) mod k. 或者您可以使用 an并且仅在初始值为负if时才添加。k

于 2012-11-22T11:59:11.627 回答
4

注意：对于数字为 的特殊情况3，很容易及时找到答案O(n log n)。

让S = sum(array).
现在，如果S % 3 == 0，那么S就是答案。
如果S % 3 == 1，那么要使总和可被您整除，3您可以删除最小的元素，或者删除最小i的i % 3 == 1元素j，k例如j % 3 == k % 3 == 2。
如果S % 3 == 2，那么您可以删除最小的i这样的i % 3 == 2，或者最小的j，k这样的j % 3 == k % 3 == 1。

于 2015-08-20T22:37:02.867 回答
0 
import java.util.*;

public class MaxSumDivisible 
{

    static int max,divisor;

public static void main(String...okok)
{
    Scanner sc=new Scanner(System.in);
    String str=sc.nextLine();
    String ss[]=str.split(" ");
    LinkedList<Integer> list= new LinkedList<Integer>();
    for(int i=0;i<ss.length;i++)
    {
        list.add(Integer.parseInt(ss[i]));
    }
    divisor=sc.nextInt();
    FindMaxSum(list,0);
    System.out.println(max);
}
public static void FindMaxSum(LinkedList<Integer> list, int currentsum)
{
    if(currentsum%divisor==0 && currentsum>max)
    {
        max=currentsum;
    }

    for(int num:list)
    {
        LinkedList<Integer> li2= new LinkedList<Integer>(list);
        li2.remove(new Integer(num));
        FindMaxSum(li2,currentsum+num);

    }
}
}

它适用于任何数字。（仅适用于 int）。

于 2015-07-27T14:08:07.307 回答
0

以下代码专门针对给定的数字 3。即。可被 3 整除的数组元素的总和。您可以进一步概括这一点。主要思想是跟踪每个 mod 3，可以达到的最大总和。时间复杂度：O(N)。空间复杂度：O(K)，其中 K 是整数，总和可以被它整除。这里 K = 3。

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        dp[1] = dp[2] = Integer.MIN_VALUE;
        for(int x : nums) {
            int[] dpNext = new int[3];
            dpNext[0] = Math.max(dp[x%3] + x, dp[0]);
            dpNext[1] = Math.max(dp[(x+1)%3] + x,dp[1]);
            dpNext[2] = Math.max(dp[(x+2)%3] + x,dp[2]);
            dp = dpNext;
        }
        return dp[0];
    }
}

LeetCode 每周竞赛 163链接到问题。

于 2019-11-17T04:31:39.427 回答