Suppose that we are given a set of n objects where the size $s$\_$i$ of the $$\backslash$textit$\{$i$\}$$th object satisfies $0$ $$<$$ $s$\_$i$ $$<$$ $1.$ We wish to pack all the objects into the minimum number of unit$-$size bins. Each bin can hold any subset of the items whose total size does not exceed $1.$ In other words, we are trying to find a function f: $$[$n$]$$ $$\backslash$rightarrow$ $$[$k$]$$ so that $$\backslash$sum$\_\{$i:f$($i$)=$j$\}$$ $s$\_$i$ $$\backslash$leq$ $1$ for all j $$\backslash$epsilon$ $$[$k$]$$$,$ and our goal is to minimize k$.$ Let S $=$ $$\backslash$sum$\_\{$i$=1\}^$n$ $s$\_$i$$\backslash \backslash$

$($a$)$ Prove that the optimal number of bins required is at least $$[$S$]$$$.\backslash \backslash$

The first$-$fit algorithm considers each object in turn $($from $1$ to n$)$ and places it in the first bin that can accommodate it$.$ If there is no such bin, then we create a new bin for it and make it the last bin. Note that this defines an ordering over bins based on when we created them, so "first" and "last" make sense.$\backslash \backslash$

$($b$)$ Prove that the first$-$fit algorithm leaves at most one bin at most half full. In other words, all bins but one are mote than half full.$\backslash \backslash$

$($c$)$ Prove that the first$-$fit algorithm is a $2-$approximation to bin packing.$\backslash \backslash$