我有一个包含 8 个元素的数组:
a[8] = {9, 7, 6, 2, 3, 1, 5, 4}
我想将 8 个元素分成 3 组。每组是 1 个或多个元素的总和。每组的总和最相似。
最佳答案
您正在描述 k-partition problem k=3。
不幸的是，已知此问题是(强)NP-Hard , 因此没有已知的有效解决方案(并且普遍认为不存在)。
您最好的希望是蛮力搜索:将所有分区创建为 3 个组，然后从中选择最好的一个。如果您正在处理 8 个元素 - 这应该是可能的，但恐怕对于更大的数组来说它很快就会变得太慢。
关于algorithm - C++ 上的拆分算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28254303/