**Next:**10.3.5
Job Shop Scheduling**Up:**10.3
Examples of some Intractable Problems**Previous:**10.3.3
Knapsack Problem

##
10.3.4 Bin Packing

Suppose we have unlimited number of bins each of unit capacity and *n*
objects with sizes *s1, s2,...,
sn *where the sizes *si(i
= 1,..., n) *are rational numbers in the range *0
< si
1*.
Optimization Problem: Determine the smallest number of bins into which
the objects can be packed and find an optimal packing.

Decision Problem: Given an integer* k*, do the objects fit in*
k *bins?

eEL,CSA_Dept,IISc,Bangalore