多路KK差分算法与贪心算法相比如何？

Question

已经证明，对于二分问题，即将n个整数集合划分为2个和相等的子集，Karmarkar-Karp差分算法始终优于贪心算法。那么这个结论是否可以扩展到k分问题呢？如果不能，是否存在贪心算法在k分问题中表现优于KK算法的例子？

- baqx0r

---

你想如何为三个或更多的分区应用差异？ - Lrrr

@Lrrr KK 启发式算法也可应用于k路划分问题中。下面是来自此论文的例子：http://ijcai.org/papers09/Papers/IJCAI09-096.pdf假设我们要将(8,7,6,5,4)划分为3个相等的子集。以下是我们将要执行的步骤：

• (8,0,0) (7,0,0) (6,0,0) (5,0,0) (4,0,0)
• (8,7,6) (5,0,0) (4,0,0)
• (5,0,0) (4,0,0) (2,1,0)* --- * 是归一化的结果
• (5,4,0) (2,1,0)
• (5,5,2)
• (3,3,0)

因此，在这个例子中，最终子集之间的差异为3。 - baqx0r

Answer 1

< p > KK算法在k路划分中并不具有普遍优越性。事实上，我们可以举出一个反例，证明贪心算法的表现更好。将集合S=[10 7 5 5 6 4 10 11 12 9 10 4 3 4 5]等分成4个子集，以最大子集和作为性能衡量标准。结果，KK算法得出[28, 26, 26, 26]，而贪心算法得出[27, 27, 27, 24]。由于28 > 27，因此这个例子中贪心算法表现更好。保留html标签。< /p >

- baqx0r

Answer 2

提供的KK算法解决方案存在问题。

• Sum（S）= 105
• Sum（[28, 26, 26, 26]）= 106
• Sum（[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算法表现更好，但这个例子不是其中之一。

- nmaass