algorithm - 多路KK差分算法与贪心算法？

Question

事实证明，Karmarkar-Karp 差分算法在2-way partitioning 问题上总是比greedy 表现更好，即分割n 个整数到 2 个总和相等的子集。这也可以扩展到k-way partitioning吗？如果不是，是否有贪心算法在 k 路划分中表现优于 KK 的示例？

Answer 1

KK 的优势不能被概括为 k 路划分。事实上，给出一个反例更容易，其中贪心算法表现更好。令性能度量为最终分区的最大子集总和。现在，取这组整数:

S = [10 7 5 5 6 4 10 11 12 9 10 4 3 4 5] 和 k=4(分成 4 个相等的子集)

快进，KK 算法 给出了 [28, 26, 26, 26] 的结果，而贪婪算法给出了 [27, 27, 27, 24] 的最终划分。由于 28 > 27，greedy 在此示例中表现更好。