Given a collection of integers and threshold value

Question

Given a collection of integers and threshold value T, divide the collection into as many groups as possible whose sum >= T.

The remaining integers (whose sum < T, so another group cannot be formed) should be left outside of the groups.

Constraints:

• length of the list <= 1,000
• values and T <= 1,000,000

Is there an algorithm for this problem in polynomial time?

For example given [25,25,25,50,50,50,10] and a threshold T = 70 it should return:

[25,50]
[25,50]
[25,50]
Remaining: [10]

Selecting [25,25,25] as one of the groups would make it possible to only form one more group, [50,50] and the remaining values would be [50,10]. Two groups are not the optimal amount of groups, which is why this solution would be incorrect.

Answer 1

There is no polynomial time algorithm for this since it contains as a special case the np-complete Partition problem.