This is for solving the 1D bin packing problem. The problem statement is: there is a list of
N
numbers, representing the widths of
N
different objects, ecah with width of
Ni. The goal is to fit all these
N objects to
M bins with fixed width of
W.
W is larger than the largest value of
Ni.
The goal is to find the minimal value of
M.
I will use both First Fit Decrease algorithm and exhaustive search to get the result. Please note that for First Fit Decrease algorithm, the time complexity is
O(N logN).
But for exhaustive search, the time complexity is
O(N!).
For
N
= 10, it will take about 20 seconds to finish. Therefore, we will ignore exhaustive search with
N
> 10.
For the sake of simplicit, we will limit ourselves to integer cases.