Разбить массив чисел по n блоков с одинаковой суммой

@Kumar6346 · Регистрация: 05.02.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте! Помогите пожалуйста решить задачку. Дан массив например:

PHP
1
$arr = array(1,4,5,9,1,2,2,3);

И этот массив надо разбить на заданное количество N блоков ТАК что бы в каждом блоке было приблизительно одинаковая (или полностью одинаковая) сумма чисел. Т.е на выходе должно получаться так.

Задаем например 3 блока и получаем - (1,4,3,1) | (5,2,2) | (9)

Реально голова уже кипит. Обгуглил все и макс. что нашел решение на питоне и то криво работающее. Помогите плиз.

@Lazy_Den · 17.07.2015, 01:20

Сообщение от Kumar6346

Реально голова уже кипит.

Не удивительно

Задача ваша из разряда так называемой Partition problem. Алгоритмы найдете по ссылке. Можно, к примеру использовать жадный алгоритм O(N log N). Вот как это будет выглядеть при разделении на две части:

Code
1
2
3
4
5
6
7
8
9
10
11
12
INPUT:  A list of integers S
OUTPUT: An attempt at a partition of S into two sets of equal sum
1  function find_partition(S):
2    A <- {}
3    B <- {}
4    sort S in descending order
5    for i in S:
6        if sum(A) < sum(B)
7            add element i to set A
8        else 
9            add element i to set B
10  return {A, B}

Вашу задачу можно описать так:

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
/*
* $in - исходный массив чисел
* $p - количество частей
*/
function divideEqualSum($in, $p = 2){
    $out = array_fill(0, $p, []); // для PHP<5.4 - $out = array_fill(0, $p, array());
    rsort($in, SORT_NUMERIC);
    foreach ($in as $v){
        usort($out, function($a, $b){
            return array_sum($a) > array_sum($b);
        });
        $out[0][] = $v;     
    }
    return $out;
}
$arr = [1,4,5,9,1,2,2,3]; // для PHP<5.4 - $arr = array(1,4,5,9,1,2,2,3); 
// по умолчанию на две части
print_r( divideEqualSum($arr) );
// на три части
print_r( divideEqualSum($arr, 3) );
// на четыре части
print_r( divideEqualSum($arr, 4) );

Добавлено через 1 минуту
И пример в песочнице

Добавлено через 6 минут
И вот еще вам пища для размышлений на эту тему.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .