Alex Varghese edited q5.tex  about 10 years ago

Commit id: 3ffcf7e907b3f4f7d43983f40cd6ade84e8b4281

deletions | additions      

       

The next part of the problem requires us to use more than one gift to satify any of the people left.  Let us look at the case where the optimal solution requires that you use two gifts per person. Our algorithm will always use the two largest gifts to satisfy the lowest person so in our case the worst optimal solution will be the one that uses the largest and smallest gift left to satify the next person. The reason this case is the worst is because our algorithm will have a lot of waste since $a_j+a_(j+1)-s_j$ $a_j+a_k-s_j$  will be as large as possible. That means we are wasting some money on this particular person. So for an example if we have 8 gifts left and 4 people left the optimal solution in the worst case is:(remember both arrays are sorted from largest to smallest)