Bin Packing Problem . One of The My Fav. Problem NP Hard

n objects to be placed in bins of capacity L each.,Determine the minimum number of bins needed to accommodate all n objects.

Given: n objects to be placed in bins of capacity L each.
Object i requires li units of bin capacity.
Objective: determine the minimum number of bins needed to
accommodate all n objects.

eg. Let L = 10
l1=5 t4==7
l2=6 t5=5
l3=3 t6=4


Data Structure Used:Array

Theorem
Bin packing problem is NP complete when formulated as a decision problem.
As an optimization problem bin packing is NP-hard

Approximation Algorithm for Bin Packing:

1. First Fit (FF)
- Label bins as 1, 2, 3, . . .
- Objects are considered for packing in the order 1, 2, 3, . . .
- Pack object i in bin j where j is the least index such that
bin j can contain object i.

2. Best Fit (BF)
Same as FF, except that when object i is to be packed, find out
that bin which after accommodating object i will have the least
amount of space left.

3. First Fit Decreasing (FFD)
reorder objects so that
li>li+1 1<=i<=n then use FF. 4. Best Fit Decreasing (BFD) reorder objects as above and then use BF. Th. Packing generated by either FF or BF uses no more then 17/10 OPT + 2 Bins That by either FFD or BFD uses no more than 11/9 OPT+ 4 Bins 1/9=9/9+2/9 This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin. It is rather simple to show this algorithm achieves an approximation factor of 2. This is due to the observation that at any given time, it is impossible for 2 bins to be at most half full. The reason is that if at some point a bin was at most half full, meaning it has at least a space of V / 2, the algorithm will not open a new bin for any item whose size is at most V / 2. Only after the bin fills with more than V / 2 or if an item with a size larger than V / 2 arrives, the algorithm may open a new bin. Thus if we have B bins, at least B − 1 bins are more than half full. Therefore \sum_{i=1}^n a_i>\tfrac{B-1}{2}V. Because \tfrac{\sum_{i=1}^n a_i}{V} is a lower bound of the optimum value OPT, we get that B − 1 < 2OPT and therefore B ≤ 2OPT.[1] See analysis below for better approximation results. float[] used = new float[n + 1]; //used[j] is the amount of space in bin j already used up. int i, j; Initialize all used entries to 0.0 Sort S into descending(nonincreasing)order, giving the sequence S1 >= S2 >= ... >= Sn.
for(i = 1; i <= n; i++)
//Look for a bin in which s[i] fits.
for(j = 1; j <= n; j++)
if (used[j]+si<+1.0)
bin[i] = j;
used[j] += si;
break; //exit for(j)
//continue for(i)


Time Complexity O(nlogn)
Space Complexity O(1)
Auxiliary Space O(n)

Run Here

Source:
A guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson
http://en.wikipedia.org/wiki/Bin_packing_problem