1
$\begingroup$

Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$ Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups.

Example: $N={20,19,18,17,14,12,9,5,4}$ and $t = 40$

Possible Grouping: ${(20,19),(18,17,4),(14,12,9,5)}$ (Greedy)

Is greedy a strategy/algorithm, that will lead to the optimal solution? If not, are there other algorithms to solve this problem?

$\endgroup$
1
$\begingroup$

I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.