0
$\begingroup$

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem.

We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < s_i < 1$ and a natural number $k > 0$.

Question: Does it exist a division of given items into $k$ boxes if every box has unit size? (The boxes don't have to be fully filled)

$\endgroup$
8
  • $\begingroup$ Are we to assume that every object is a cube? A long, thin pencil may have size $\frac 12$ but it can't be fit into a unit cube. $\endgroup$
    – lulu
    Commented May 11, 2016 at 14:50
  • $\begingroup$ @lulu: I would expect each object to be a $1 \times 1 \times s_i$ cuboid so you can ignore all but one of the dimensions $\endgroup$
    – Henry
    Commented May 11, 2016 at 14:54
  • $\begingroup$ Well, it's clearly possible if $k \geq n$. If $k < n$, I'm not sure what can be said about the problem in general. $\endgroup$
    – DylanSp
    Commented May 11, 2016 at 14:54
  • $\begingroup$ @Henry You may well be right...certainly that's a sensible assumption. But I'm not sure it's self-evident. Maybe the OP can confirm? $\endgroup$
    – lulu
    Commented May 11, 2016 at 14:55
  • $\begingroup$ Are you asking how to prove that the problem is NP-Complete or are you asking for an algorithm to solve the problem? $\endgroup$
    – user137481
    Commented May 11, 2016 at 15:17

2 Answers 2

Reset to default
1
$\begingroup$

This is called the bin packing problem. It is considered computationally hard in general to get an exact answer, but approximate algorithms exist (i.e. ones that find an answer that is provably close to best).

$\endgroup$
0
$\begingroup$

Partition Problem
$\quad$Input: A list L of n integers $i_1,...,i_n$
$\quad$Question: Is there a partition of L into 2 lists, $L_1$ and $L_2$ such that $\sum_{i \in L_1}i = \sum_{i \in L_2}i?$

Given an instance of Partition P, create an instance of Bin Packing BP by:

1) Set $k = 2$
2) Set $C = \sum_{i \in L} i$
3) Set $s_j = \frac{2i_j}{C}$

Note that $\sum s_j = 2$

P is a "Yes" instance $\Rightarrow$ BP is a "Yes" instance
$\quad$If there is a partition of L into $L_1$ and $L_2$ then the $s_j$ can be partitioned into 2 lists each
$\quad$summing to $1$. Hence, they can fit into $k=2$ bins.

BP is a "Yes" instance $\Rightarrow$ P is a "Yes" instance
$\quad$If the $s_j$ can be fit into k = 2 bins, since $\sum s_j = 2$, the sum of the $s_j$ in each bin must be equal.
$\quad$Let $L_1$ be a list of $i_j$ corresponding to $s_j$ in one of the bins.
$\quad$Let $L_2$ be a list of $i_j$ corresponding to $s_j$ in the other bin.
$\quad$So, there exists a partition of L into $L_1$ and $L_2$ such that $\sum_{i \in L_1}i = \sum_{i \in L_2}i$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .