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?

  • $\begingroup$ 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. $\endgroup$ – CIAndrews Mar 24 '19 at 11:43
  • $\begingroup$ @CIAndrews I updated the question. $\endgroup$ – Manoharsinh Rana Mar 24 '19 at 11:45
  • $\begingroup$ @Apass.Jack I updated the question. $\endgroup$ – Manoharsinh Rana Mar 24 '19 at 12:04
  • 2
    $\begingroup$ It's not poly-time solvable even for $K=2$, since that's the Partition Problem. $\endgroup$ – j_random_hacker Mar 24 '19 at 12:05
  • 2
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Mar 24 '19 at 17:42

Since the number of bins is fixed, the problems boils down to a job shop scheduling with atomic jobs. See https://en.wikipedia.org/wiki/Job_shop_scheduling#Atomic_jobs

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.

EDIT after request on polynomial time Since it's equivalent to the partition problem, which is NP-hard, this problem is also NP-hard and therefore not solvable in polynomial time.

  • $\begingroup$ But here the size of the bins should be the same. $\endgroup$ – Manoharsinh Rana Mar 24 '19 at 12:15
  • $\begingroup$ The size yes, but the integer value / weight is not the same. $\endgroup$ – CIAndrews Mar 24 '19 at 12:16

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.