3
$\begingroup$

I've been trying to solve an interesting problem created by one of my friends. The following is the problem statement:

There are $n$ types of chocolates. $\langle a_1,a_2,a_3....a_n \rangle$ are positive integers which represent the number of chocolates of each type. These chocolates must be packed into boxes of capacity $k$ i.e. each box can contain at most $k$ chocolates. Also no box can contain two chocolates of the same type i.e. the chocolates in every box must be of distinct types. What is the minimum number of boxes needed to pack all the chocolates?

A greedy approach would be to iteratively fill boxes by picking chocolates from the top $k$ types (in terms of number of remaining chocolates). However this is not of polynomial time complexity.

I also tried to solve the decision version of the problem. (can the chocolates be packed using $m$ boxes ?). I was able to model it as a max flow problem but the number of vertices was not polynomial in the input size.

Is this problem NP-Complete? If not what would be a good polynomial time algorithm to solve it?

$\endgroup$
1
$\begingroup$

The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as there are any chocolates left, fill a box with one of each of the chocolates. That solution is linear in the number of chocolate pieces but unfortunately not linear in the problem size. So instead of doing the greedy algorithm, we simulate how it would run and calculate how many boxes would be filled, in polynomial time.

Let $x_i$ be the number of pieces of type $a_i$. Sort in descending order, then remove the chocolates where $x_i$ = 0. If n ≤ k you need $x_1$ boxes.

As long as $x_k$ > $x_{k+1}$ you would put chocolates $a_1$ to $a_k$ into a box. This fills $x_k - x_{k+1}$ boxes, and you decrease $x_1$ to $x_k$ by $x_k - x_{k+1}$. You simulate this in constant time.

After that you have $x_1$ to $x_j$ greater than $x_k$, and $x_{j+1}$ to $x_m$ equal to $x_k$, for some j < k and m > k. So you have a larger number of j chocolates, and an equal number of m-j chocolates, m > k. You would fill m-j boxes by putting m-j of the chocolates $a_1$ to $a_j$ into each box, and filling with k-j of the chocolates $a_{j+1}$ to $a_m$.

You would do that t times. t is limited: With each round of m-j boxes, the number of the top j chocolates is reduced by m-j, the next chocolates are reduced by k-j. The difference is reduced by t (m-k), so t ≤ $(x_j - x_{j+1}) / (m-k)$. The next chocolates are reduced by t (k-j), so t ≤ $(x_m - x_{m+1}) / (k-j)$, letting $x_{m+1} = 0$ if m = n. You take the largest possible t and simulate t (m-j) steps in constant time.

When this is done (and t may be 0) we remove all chocolates with a zero count, and we may be done. If not, then we do one simulation step which will change the situation, and start all over.

That's the idea. You can probably clean this up a bit.

$\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.