0

给一个 Set S，将集合划分为k不相交的子集，使得它们的总和之差最小。

说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。

该问题类似于The Algorithm Design Manual中的The Partition Problem。除了Steven Skiena讨论了一种无需重新排列即可解决它的方法。

我打算尝试模拟退火。所以我想知道，是否有更好的方法？

提前致谢。

4

2 回答 2

3

背包的伪多时间算法可用于k=2. 我们能做的最好的就是 sum(S)/2。运行背包算法

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

然后查看 sum(S)/2，然后是 sum(S)/2 +/- 1，等等。

对于 'k>=3' 我相信这是 NP 完全的，就像 3 分区问题一样。

对 k>=3 执行此操作的最简单方法就是暴力破解，这是一种方法，不确定它是最快的还是最干净的。 

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);

模拟退火可能很好，但由于特定解决方案的“邻居”并不十分清楚，因此遗传算法可能更适合于此。您首先会随机选择一组子集，然后通过在子集之间移动数字来“变异”。

于 2011-03-28T20:26:45.023 回答
0

如果集合很大，我肯定会选择随机搜索。在写“邻里没有明确定义”时，不知道 spin_plate 的确切含义。当然是 --- 你要么将一个项目从一个集合移到另一个集合，要么从两个不同的集合交换项目，这是一个简单的邻域。我会在随机搜索中使用这两种操作（实际上可能是禁忌搜索或模拟退火。）

于 2011-04-06T05:42:08.660 回答