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

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 分区问题而另一个这样的子集则没有。