C++ 上的拆分算法

Question

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

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

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

Answer 1

您正在用 k=3 描述 k-partition problem。

不幸的是，这个问题已知是（强）NP-Hard，因此没有已知的有效解决方案（并且一般相信是不存在的）。

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