最大非相邻数组元素和可被K整除

Question

3

给定一个包含n个元素的数组ar，找到能够被K整除的最大和。求和中使用的元素不需要连续。

例如，对于N = 4，ar = [2,2,1,2]和K = 3，答案将是6（包括元素2、2和2）。

- Shashank

求和元素的数量是否受到K的限制？ - FireAlkazar

1

有趣的问题。我猜第一步是对每个元素取模，将它们缩小到有限域内。但这只是准备工作，在你的例子中甚至不需要。哇，我只能想到通过试错来解决，进行（2^n）-1次操作，其中n是数组中元素的数量，但当我们找到一个组合X满足X+1的模等于0时停止。但肯定有更好的方法。 - WDS

@Henry - 抱歉，可能我让问题含糊不清了。最后一部分是最大总和应该可以被K整除。 - Shashank

1

所以这与模算术无关，这是我读标题的方式。我已经更新了问题。 - M Oehm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

这只是子集和问题。

令dp[i] = true表示我们可以构建和为i，否则为false。

dp[0] = true
s = 0
for each number x in the array:
  s += x
  for j = s down to x
    dp[j] = dp[j] OR dp[j - x]

然后找到最大的j <= s，使得j % k == 0且dp[j] == true。