Karmarkar-karp差分算法是如何工作的？

有人能給我karmarkar-karp差分算法的僞代碼，我不明白。如果有可視化/演示的話，那就更好了。Karmarkar-karp差分算法是如何工作的？

來源

2010-10-08 blahster

+1。 ...並可選擇更新維基百科，以使其讀者受益於更好的解釋（http://en.wikipedia.org/wiki/Partition_problem#Methods）。 :) – EOL 2010-10-08 11:04:32

http://www.americanscientist.org/issues/pub/the-easiest-hard-problem/2似乎解釋得很好，特別是在最後一幅圖中。 – AakashM 2010-10-08 11:12:04

你可以找到一個例證：

http://www.americanscientist.org/include/popup_fullImage.aspx?key=plqy+ZGbKkFxkacwUJPk/RRQWP4HNcaJ

來源

2011-02-04 20:38:15 Kurosh

它還通過降序排序號開始。

這裏是列表[8,7,6,5,4]

的排序結果在每個步驟中，該算法致力於將兩個最大數在不同的子集，同時推遲決定哪些每個子集都會進入。
在上面的例子中，如果我們在左側子集中放置8，在右側子集中放置7，這相當於將它們的差分放置在左側子集中，因爲我們可以從中減去7 兩個子集都不會影響最終的差異。類似地，將8 放置在右側子集中並將7放置在左側子集中相當於在右側子集中放置1。該算法刪除兩個最大的數字，計算它們的差異，然後像其他任何數字一樣處理差異爲，並在剩餘數字列表中按排序順序插入差異。該算法繼續刪除兩個最大的數字，將它們替換爲它們在排序列表中的差異，直到剩下僅一個數字，其中是最終子集差異的值。

例如，給定分選的整數（8,7,6,5,4）時，圖8和7通過它們的1差，其被插入在剩餘的列表所替換，產生（6 ，5,4,1）。接下來，將6和5替換爲它們的差值1，產生（4,1,1）。將4和1替換爲它們的差值3，給出（3,1）和最終這些差值最後兩個數字是最後的子集差異爲2. KK啓發式在這種情況下也未能找到最佳分區，但比貪婪啓發式更好。

數劃分問題Download PDF

來源

2013-02-18 13:44:53 lyfing

Karmarkar-karp差分算法是如何工作的？

回答

相關問題