In case of given m elements of different weights and bins each of capacity C, assign each element to a bin so that number of total implemented bins is minimized. Assumption should be that all elements have weights less than bin capacity.

Applications

Placing data on multiple disks.

Loading of containers like trucks.

Packing advertisements in fixed length radio/TV station breaks.

Job scheduling.

Example

Input: weight[] = {4, 1, 8, 1, 4, 2}

Bin Capacity c = 10

Output: 2

We require at least 2 bins to accommodate all elements

First bin consists {4, 4, 2} and second bin {8, 2}

Lower Bound

We can always calculate a lower bound on minimum number of bins required using ceil() function. The lower bound can be given below −

Bins with minimum number >= ceil ((Total Weight) / (Bin Capacity))

In the above example, lower bound for first example is “ceil(4 + 1 + 8 + 2 + 4 + 1)/10” = 2