将整数数组分解为具有精确和的最大子数组数

Question

如果我有像这样的整数数组...

{3,5,5,6,6,6,6,6,6,7,7,8,8,8,9,9,9}

我想创建最大数量的子数组，这些子数组加起来正好是 40，每个元素只使用一次。只要不是所有的重复都被使用，重复数字就可以了。

找到最大数量的子数组和找到 40 的子数组很容易，但是问题是找到提供 40 的子数组并且不会阻止形成其他 40 的子数组。

我需要形成子集的输出。

听起来和分区问题很像。

这个问题有名字吗？有人有解决方案吗？

Answer 1

也许效率不高，但您可以执行以下操作 -- 找到可以解决子集和问题的 40 的倍数，从 40 <= 总和的最大倍数开始，然后向下计算。然后，一旦找到总和为 40 的倍数的子集，就为该子集解决适当的 k 分区问题。例如，如果 40 的倍数是 120，请解决（如果可能的话）将其分成 3 组大小相等的 3 分区问题。但请注意，在排除 120 的解决方案之前，仅确定总和为 120 的单个子集是不够的——您必须查看总和为 120 的所有子集，因为这样的一个子集可能有一个可解决的 3 分区问题而另一个这样的子集则没有。

Answer 2

你可以使用动态规划。让dp[j]- the max number of segments that sum to 40 s.t. no index of segments is larger than j。然后您可以执行以下操作：

for(int i = 0; i < numbers.size(); i++)
    for(int j = i, sum = numbers[j]; j >= 0 && sum <= 40; j--, sum += numbers[j]) {
        if(sum == 40) {
            dp[i] = max(dp[i], j > 0 ? dp[j-1] : 0);
        }
    } 

int answer = 0;
for(int i = 0; i < dp.size(); i++)
    answer = max(answer, dp[i]);

我认为代码应该是不言自明的。

将整数数组分解为具有精确和的最大子数组数

Break an Array of Integers into the Maximum Number of Subarrays with Exact Sums

arrays

algorithm

discrete-mathematics