0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Mar 24, 2019 at 11:43
  • 2
    $\begingroup$ It's not poly-time solvable even for $K=2$, since that's the Partition Problem. $\endgroup$
    – j_random_hacker
    Commented Mar 24, 2019 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
    Commented Mar 24, 2019 at 17:42

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.