Разделение предметов на две кучи одинакового веса

Question

Я уверен, что вы уже слышали об этой проблеме.Учитывая список натуральных чисел, возможно ли разделить их на две стопки равных сумм?Если да, напишите две строки с объектами в каждой стопке.

Это известная проблема?У него есть имя?Это NP-Complete?Если нет, то какое самое быстрое решение?

Answer 1

Это проблема Partition , которая является NP-Complete. Это вариант Подмножества СУММ.

Какой самый быстрый, действительно зависит от данных, которые вы имеете. Например, если они ограничены, вы можете использовать динамическое программирование и т. Д.