Учитывая набор целых чисел и пороговое значение T, разделите набор на как можно больше групп, сумма которых >= T.
Оставшиеся целые числа (сумма которых ‹ T, поэтому нельзя составить другую группу) должны быть оставлены вне групп.
Ограничения:
- длина списка ‹= 1000
- значения и T ‹= 1 000 000
Есть ли алгоритм решения этой задачи за полиномиальное время?
Например, учитывая [25,25,25,50,50,50,10] и порог T = 70, он должен вернуть:
[25,50]
[25,50]
[25,50]
Remaining: [10]
Выбор [25,25,25] в качестве одной из групп позволит сформировать только еще одну группу, [50,50], а остальные значения будут [50,10]. Две группы — не оптимальное количество групп, поэтому такое решение будет неверным.
