# invariant of bin packing

We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We need to find the size of bin such that wastage of unused bin is minimized.

Is this problem polynomial time solvable?

• If there is no condition on the number of bins or the capacity and the weight is determined by the integer value, you can choose 1 bin with the sum of the set as capacity. That gives a wastage of 0 whereas every existing bin has the same capacity. – CIAndrews Mar 24 at 11:43
• @CIAndrews I updated the question. – Manoharsinh Rana Mar 24 at 11:45
• @Apass.Jack I updated the question. – Manoharsinh Rana Mar 24 at 12:04
• It's not poly-time solvable even for $K=2$, since that's the Partition Problem. – j_random_hacker Mar 24 at 12:05
• Spelling that out to you would take away any remaining learning value in this exercise. Spend some time and effort and see if you can figure the correspondence out yourself, and come back with specific questions if you get stuck. – j_random_hacker Mar 24 at 17:42

A solution is given by $$\max\{ 1/m \sum_{i=1}^n t_i, max_i t_i \}$$ where $$t_i$$ represents the $$i$$th integer and $$m$$ represent the set length. The wiki reference above includes a paper with the proof.