разделительный список на куски сбалансированного веса

Question

Мне нужен алгоритм для разбиения списка значений на такие чанки, чтобы сумма значений в каждом чанке была ( приблизительно ) равна (ее некоторое изменение проблема ранца , Iпредположим)

Так, например, [1, 2, 1, 4, 10, 3, 8] => [[8, 2], [10], [1, 3, 1, 4]]

Куски одинаковой длины предпочтительны, но это не ограничение.

Python является предпочтительным языком, но приветствуются и другие

Редактировать: Количество чанков определено

Answer 1

Жадный:
1. Заказ доступных предметов по убыванию.
2. Создайте N пустых групп
3. Начните добавлять элементы по одному в группу с наименьшей суммой.

Я думаю, в большинстве реальных ситуаций этого должно быть достаточно.

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

Answer 3

На основе ответа @Alin Purcaru и замечаний @amit я написал код (Python 3.1).Насколько я тестировал, он имеет линейную производительность (как по количеству элементов, так и по количеству кусков, так что в конечном итоге это O (N * M)).Я избегаю сортировки списка каждый раз, сохраняя текущую сумму значений для каждого чанка в dict (может быть менее практичным при большем количестве чанков)

import time, random

def split_chunks(l, n):
    """ 
       Splits list l into n chunks with approximately equals sum of values
       see  /6484322/razdelitelnyi-spisok-na-kuski-sbalansirovannogo-vesa
    """
    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 (в 2–3 раза медленнее, чем в Python 3.1):

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 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),...}

Теперь вы можете использовать крутое восхождение на гору со случайным перезапуском.

этот алгоритм будет в любое время Это означает, что вы можете начать поиск, а когда закончится время - остановите его, и вы получите лучший результат.результат будет лучше по мере увеличения времени выполнения.