How does the Karmarkar-karp differencing algorithm work?

Can somebody开发者_JAVA技巧 give me pseudocode of karmarkar-karp's differencing algorithm, I don't understand it. Better if there's a visualization/demo of it.

It also begins by sorting the numbers in decreasing order.

Here is a sorting result of list [8,7,6,5,4]

At each step, the algorithm commits to placing the two largest numbers in different subsets, while deferring the decision about which subset each will go in.
In the above example,if we place 8 in the left subset, and 7 in the right subset, this is equivalent to placing their difference of 1 in the left subset, since we can subtract 7 from both subsets without affecting the final difference. Similarly, placing 8 in the right subset and 7 in the left subset is equivalent to placing 1 in the right subset. The algorithm removes the two largest numbers, computes their difference, and then treats the difference just like any other number to be assigned, inserting it in sorted order in the remaining list of numbers. The algorithm continues removing the two largest numbers, replacing them by their difference in the sorted list, until there is only one number left, which is the value of the final subset difference.

For example, given the sorted integers (8,7,6,5,4), the 8 and 7 are replaced by their difference of 1, which is inserted in the remaining list, resulting in (6,5,4,1). Next, the 6 and 5 are replaced by their difference of 1, yielding (4,1,1).The 4 and 1 are replaced by their difference of 3, giving (3,1), and finally the difference of these last two numbers is the final subset difference of 2. The KK heuristic also fails to find the optimal partition in this case,but does better than the greedy heuristic.

Number partition problem Download PDF