Division n items into k boxes prove that it is NP-Complete

Question

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)

Answer 1

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).

Answer 2

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$