将列表分割为均衡权重的块

Question

我需要一个算法，把一组数分成几个小组，使得每个小组里的数加起来的总和大致相等（这有点像背包问题，我想）。

举个例子，像这个列表 [1, 2, 1, 4, 10, 3, 8]，可以分成 [[8, 2], [10], [1, 3, 1, 4]] 这样的组合。

最好是每个小组的长度相等，但这不是必须的。

我比较喜欢用 Python 来实现，不过其他语言也可以。

补充一下：小组的数量是固定的

Answer 1

这样做会更快，而且看起来更简洁一些（基于上面的想法！）

def split_chunks2(l, n):
    result = [[] for i in range(n)]
    sums   = [0]*n
    i = 0
    for e in l:
        result[i].append(e)
        sums[i] += e
        i = sums.index(min(sums)) 
    return result

Answer 2

根据@Alin Purcaru的回答和@amit的评论，我写了段代码（Python 3.1）。根据我的测试，它的性能是线性的（无论是项目数量还是块的数量，最终的复杂度是O(N * M)）。我避免每次都对列表进行排序，而是把每个块的当前值总和保存在一个字典里（如果块的数量很多，这种方法可能不太实用）。

import time, random

def split_chunks(l, n):
    """ 
       Splits list l into n chunks with approximately equals sum of values
       see  http://stackoverflow.com/questions/6855394/splitting-list-in-chunks-of-balanced-weight
    """
    result = [[] for i in range(n)]
    sums   = {i:0 for i in range(n)}
    c = 0
    for e in l:
        for i in sums:
            if c == sums[i]:
                result[i].append(e)
                break
        sums[i] += e
        c = min(sums.values())    
    return result


if __name__ == '__main__':

    MIN_VALUE = 0
    MAX_VALUE = 20000000
    ITEMS     = 50000
    CHUNKS    = 256

    l =[random.randint(MIN_VALUE, MAX_VALUE ) for i in range(ITEMS)]

    t = time.time()

    r = split_chunks(l, CHUNKS)

    print(ITEMS, CHUNKS, time.time() - t)

顺便说一下，因为我们可以，所以我用PHP 5.3写了相同的代码（速度比Python 3.1慢2到3倍）：

function split_chunks($l, $n){

    $result = array_fill(0, $n, array());
    $sums   = array_fill(0, $n, 0);
    $c = 0;
    foreach ($l as $e){
        foreach ($sums as $i=>$sum){
            if ($c == $sum){
                $result[$i][] = $e;
                break;  
            } // if
        } // foreach
        $sums[$i] += $e;        
        $c = min($sums);
    } // foreach
    return $result;
}

define('MIN_VALUE',0);
define('MAX_VALUE',20000000);
define('ITEMS',50000);
define('CHUNKS',128);

$l = array();
for ($i=0; $i<ITEMS; $i++){
    $l[] = rand(MIN_VALUE, MAX_VALUE);  
}

$t = microtime(true);

$r = split_chunks($l, CHUNKS);

$t = microtime(true) - $t;

print(ITEMS. ' ' .  CHUNKS .' ' . $t . ' ');

Answer 3

贪心算法:
1. 把可用的物品按大小从大到小排列。
2. 创建N个空的组。
3. 开始一个一个地把物品放进当前总和最小的组里。

我觉得在大多数现实生活的情况下，这样做就足够了。