Разделить послед-сть чисел на две примерно равные по суммам

[hardfun]

Здравствуйте.

Допустим, есть вот такое множество натуральных чисел: $M=\{1,1,1,2,3,5,5,8\}$, сумма их = 26
Требуется найти все пары подмножеств $M_1, M_2, M_1 \cup M_2 = M, такие что разница сумм их элементов по модулю будет минимальная, т.е.
$$|\sum\limits_ia_i - \sum\limits_kb_k|\to min~(a_i - \text{элементы}~ M_1, b_k - \text{элементы}~M_2)$
Для примера выше:
$M_1=\{8,5\},~M_2=\{1,1,1,2,3,5\}$
$M_1=\{8,1,1,1,2\}, ~ M_2=\{3,5,5\}$
$M_1=\{8,2,3\},~ M_2=\{1,1,1,5,5\}$
etc
Перестановка значений внутри подмножеств, а также перестановка самих множеств местами, - не считается новой комбинацией.

К какому классу относится данная задача ? Где почитать про алгоритмы её решения ?

[Kallikanzarid]

Пометьте как-нибудь различные единицы и пятерки, исключительно порядка ради :)

[ИСН]

Пахнет чем-то полнопереборным.

[hardfun]

> Пометьте как-нибудь различные единицы и пятерки, исключительно порядка ради :)
ну пусть так: {$1_1, 1_2, 1_3, 2, 3, 5_1, 5_2, 8$}
дальше всё равно вопрос остался: куда рыть, к какому классу относится эта задача ?

[Toucan]

Немного поправил формулы и вернул.

hardfun,
формулы с фигурными скобками набираются так:
$M_1=\{8,5\},~M_2=\{1,1,1,2,3,5\}$

$M_1=\{8,5\},~M_2=\{1,1,1,2,3,5\}$

[Евгений Машеров]

Решайте динамическим программированием.
http://rain.ifmo.ru/cat/view.php/theory ... pprox-2004

-- Пт апр 22, 2011 21:54:47 --

"Задача о суммах подмножеств"