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