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?
Packing chocolate boxes
algorithms;complexity theory;optimization;time complexity;packing