多路KK差分算法与贪心算法？
Multi-way KK differencing algorithm vs. Greedy algorithm?
事实证明，Karmarkar-Karp 的差分算法 对于 2 向划分总是比 greedy 表现更好 个问题，即将 n 个整数的集合划分为 2 个总和相等的子集。这也可以扩展到 k 向分区 吗？如果不是，是否有贪心算法在 k 向划分中表现优于 KK 的例子？
KK 的 优势不能 推广到 k 路分区。事实上，给出一个 Greedy algorithm 表现更好的反例更容易。
令性能度量为最终分区的最大子集总和。
现在，取这组整数：
S = [10 7 5 5 6 4 10 11 12 9 10 4 3 4 5] 和 k=4（分成 4 个相等的子集）
快进，KK算法给出了[28,26,26,26]的结果，而greedy给出了[27,27,27,24]的最终划分.由于 28 > 27，greedy 在此示例中表现更好。
提供的 KK 算法解决方案存在问题。
- 总和(S) = 105
- 总和([28, 26, 26, 26]) = 106
- 总和([27, 27, 27, 24]) = 105
贪心算法给出的结果为
{{12, 6, 5, 4}{11, 7, 5, 4}{10, 10, 4, 3}{10, 9, 5}}
[27, 27, 27, 24]
KK算法给出的结果为
{{5, 12, 6, 4}{5, 10, 7, 4}{5, 11, 10}{4, 3, 10, 9}}
[27, 26, 26, 26]
由于最高和相等（27=27）且KK的最低和大于贪心算法的（26>24），所以KK算法表现更好。在某些情况下，贪心算法仍然可以比 KK 表现得更好，但这个例子不是其中之一。
事实证明，Karmarkar-Karp 的差分算法 对于 2 向划分总是比 greedy 表现更好 个问题，即将 n 个整数的集合划分为 2 个总和相等的子集。这也可以扩展到 k 向分区 吗？如果不是，是否有贪心算法在 k 向划分中表现优于 KK 的例子？
KK 的 优势不能 推广到 k 路分区。事实上，给出一个 Greedy algorithm 表现更好的反例更容易。 令性能度量为最终分区的最大子集总和。 现在，取这组整数：
S = [10 7 5 5 6 4 10 11 12 9 10 4 3 4 5] 和 k=4（分成 4 个相等的子集）
快进，KK算法给出了[28,26,26,26]的结果，而greedy给出了[27,27,27,24]的最终划分.由于 28 > 27，greedy 在此示例中表现更好。
提供的 KK 算法解决方案存在问题。
- 总和(S) = 105
- 总和([28, 26, 26, 26]) = 106
- 总和([27, 27, 27, 24]) = 105
贪心算法给出的结果为
{{12, 6, 5, 4}{11, 7, 5, 4}{10, 10, 4, 3}{10, 9, 5}}
[27, 27, 27, 24]
KK算法给出的结果为
{{5, 12, 6, 4}{5, 10, 7, 4}{5, 11, 10}{4, 3, 10, 9}}
[27, 26, 26, 26]
由于最高和相等（27=27）且KK的最低和大于贪心算法的（26>24），所以KK算法表现更好。在某些情况下，贪心算法仍然可以比 KK 表现得更好，但这个例子不是其中之一。