Bob has n computer files which he needs to save on to his K hard disks. The files have sizes

s$1,$ s$2,,$ sn$,$ and the hard disks have identical size T $.$ Bob wants to know whether there is a way

to put all files into hard disks without cutting any file into pieces.

$1$

$1.(10$ pts$)$ Finding the minimum Kopt such that all files can be saved on to Kopt many hard disks

is NP$-$complete $($you don$$t have to prove it$).$ So Bob wants to find an efficient approximation

algorithm for it$.$ Help Bob come up with an efficient $2-$approximation algorithm for this

problem, and prove its correctness and running time.

$2.($Optional$)$ Prove that for any $>0,$ there is no polynomial$-$time algorithm that gives a$(3$

$2$ $)-$approximation unless P $=$ NP