Given: n objects to be placed in bins of capacity L each.

Object i requires units of bin capacity.

Objective: determine the minimum number of bins needed to

accommodate all n objects.

eg. Let L = 10,

**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

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 than bins.

That by either FFD or BFD uses no more than

Thu May 13 13:03:52 EDT 1999