C++上的拆分算法

Question

我有一个包含 8 个元素的数组：

a[8] = {9, 7, 6, 2, 3, 1, 5, 4}

我想将 8 个元素分成 3 组。每个组是 1 个或多个元素的总和。每个组的总和最相似。

Answer 1

你描述的是 k=3 的 k 分区问题。

不幸的是，这个问题已知是（强）NP-Hard，所以没有已知的有效解决方案（并且一般

认为不存在）。

你最大的希望将是暴力搜索：将所有分区创建为3组，并从中选择最好的一个。如果您正在处理 8 个元素 - 这应该是可能的，但恐怕对于更大的数组来说很快就会变得太慢。