赋予一组取值，分区设置为 K 不相交的子集，使得它们的和的差异很小

Give a Set S, partition the set into k disjoint subsets such that the difference of their sums is minimal.

说， S = {1,2,3,4,5} 和 K = 2 ，所以 {{3,4}，{1,2,5}} ，因为它们的和 {7,8} 有最小差异。对于 S = {1,2,3}，K = 2 这将是 {{1,2}，{3}} 自总之不同的是 0 。

say, S = {1,2,3,4,5} and k = 2, so { {3,4}, {1,2,5} } since their sums {7,8} have minimal difference. For S = {1,2,3}, k = 2 it will be {{1,2},{3}} since difference in sum is 0.

现在的问题是类似的的的算法设计手册的划分问题的的。除了史蒂芬Skiena 的讨论的方法来解决它的不重排。

The problem is similar to The Partition Problem from The Algorithm Design Manual. Except Steven Skiena discusses a method to solve it without rearrangement.

我要尝试模拟退火。所以我想，如果有一个更好的方法？

I was going to try Simulated Annealing. So i wondering, if there was a better method?

在此先感谢。

推荐答案

伪polytime算法的背包可用于 K = 2 。我们能做的最好的总和（S）/ 2。运行背包算法

The pseudo-polytime algorithm for a knapsack can be used for k=2. The best we can do is sum(S)/2. Run the knapsack algorithm

for s in S:
    for i in 0 to sum(S):
        if arr[i] then arr[i+s] = true;

再看看总和（S）/ 2，然后求和（S）/ 2 +/- 1，等等。

then look at sum(S)/2, followed by sum(S)/2 +/- 1, etc.

有关'K> = 3我相信这是一个NP完全一样，三分区的问题。

For 'k>=3' I believe this is NP-complete, like the 3-partition problem.

要做到这一点对于k> = 3，最简单的办法就是暴力破解它，这里有一个方法，不知道这是否是最快或最干净的。

The simplest way to do it for k>=3 is just to brute force it, here's one way, not sure if it's the fastest or cleanest.

import copy
arr = [1,2,3,4]

def t(k,accum,index):
    print accum,k
    if index == len(arr):
        if(k==0):
            return copy.deepcopy(accum);
        else:
            return [];

    element = arr[index];
    result = []

    for set_i in range(len(accum)):
        if k>0:
            clone_new = copy.deepcopy(accum);
            clone_new[set_i].append([element]);
            result.extend( t(k-1,clone_new,index+1) );

        for elem_i in range(len(accum[set_i])):
            clone_new = copy.deepcopy(accum);
            clone_new[set_i][elem_i].append(element)
            result.extend( t(k,clone_new,index+1) );

    return result

print t(3,[[]],0);

模拟退火可能是很好的，但由于特定的解决方案中的邻居是不是真的清楚，遗传算法可能更适合这个。你会通过亚群之间的移动号码，随机挑选一组子集和发生变异开始了。

Simulated annealing might be good, but since the 'neighbors' of a particular solution aren't really clear, a genetic algorithm might be better suited to this. You'd start out by randomly picking a group of subsets and 'mutate' by moving numbers between subsets.