将列表平衡拆分成多个块

Question

我需要一个算法来将值列表分成这样的块，使得每个块中的值的总和（大致）相等（我想这是背包问题的一些变体）。

例如，[1, 2, 1, 4, 10, 3, 8] => [[8、2]，[10]，[1、3、1、4]]

等长的块被优先考虑，但这不是一个限制。

Python 是首选语言，但其他语言也可以。

编辑：定义了块的数量。

- ts.

---

很抱歉，您的问题定义不清楚。是否有要求块数与完全相等总和的偏差？目前这个问题的解决方案是只有一个块，非常简单。 - Petar Ivanov

它闻起来是NP难的。你应该定义什么是“近似”，因为我相信没有多项式解决方案可以找到最佳分区。 - amit

@Petar Ivanov：我已经在编辑中明确指出 - 块的数量已定义。 - ts.

这是广义的划分问题：http://en.wikipedia.org/wiki/Partition_problem，它是NP完全问题。 - carl

@ts：@Alin的答案提供了这个近似值。如果足够好，就采用它；如果不行，可以尝试使用人工智能工具来解决这个问题。 - amit

Answer 1

贪心算法：
1. 将可用项目按降序排序。
2. 创建N个空分组。
3. 逐个将项目添加到当前和最小的分组中。

我认为在大多数实际情况下，这应该足够了。

- Alin Purcaru

---

O(NlogN)。排序是瓶颈，这个解决方案将确保两组之间的差异最多为max{S}。 - amit

在另一个线程中，类似于这个，我已经证明了max{S}-min{S}是该算法的最大差异。看一下：https://dev59.com/QVjUa4cB1Zd3GeqPSY6U#6486812 - amit

@amit。将[1, 1, 1]分成两个块怎么样？我认为max(S)听起来更像是正确的答案。 - Mad Physicist

Answer 2

这样做会更快，而且更加简洁（基于以上想法！）

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

- foxtrotmikew

---

鉴于没有提供任何解释，一些标识符可能更具说明性。 - guidot

Answer 3

根据@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  https://dev59.com/Kmw15IYBdhLWcg3wD3jp
    """
    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 . ' ');

- ts.

---

在一个不同的线程中，类似于这个，我已经证明了max{S}-min{S}是该算法的最大差值。看一下：https://dev59.com/QVjUa4cB1Zd3GeqPSY6U#6486812 - amit

Answer 4

你可能想要使用人工智能工具来解决问题。首先需要定义你的问题。

States={(c1,c2,...,ck) | c1,...,ck are subgroups of your problem , and union(c1,..,ck)=S } 
successors((c1,...,ck)) = {switch one element from one sub list to another } 
utility(c1,...,ck) = max{sum(c1),sum(c2)...} - min{sum(c1),sum(c2),...}

现在，您可以使用带有随机重启的最陡上升爬山算法。

该算法将是任何时候的，这意味着您可以开始搜索，当时间到了就停止，然后您将得到迄今为止的最佳结果。随着运行时间的增加，结果会更好。

- amit

Answer 5

foxtrotmikew答案的Scala版本：

def workload_balancer(element_list: Seq[(Long, Any)], partitions: Int): Seq[Seq[(Long, Any)]] = {
    val result  = scala.collection.mutable.Seq.fill(partitions)(null : Seq[(Long, Any)])
    val index   = (0 to element_list.size-1)
    val weights = scala.collection.mutable.Seq.fill(partitions)(0l)
    (0 to partitions-1).foreach( x => weights(x) = 0 )

    var i = 0
    for (e <- element_list){
      result(i)  = if(result(i) == null) Seq(e) else result(i) ++: Seq(e)
      weights(i) = weights(i) + e._1
      i          = weights.indexOf( weights.min ) 
    }
    result.toSeq
}

element_list 应该是 (weight: Long, Object: Any)，这样你就可以将对象排序并分成不同的工作负载（结果）。它对我帮助很大！谢谢。

- IQR