Problem $5.$ Greedy $==$ Optimal? $(10$ points$)$

In one of the two Tatte problems, you found that the greedy strategy did well; your greedy choice

was either the rating of an item, or rating$-$per$-$dollar. Now your job is to show that the greedy

choice you made does yield an optimal solution.

$($a$)$ In which problem above did you find that Greedy gave you a pretty good solution? Was your

greedy choice rating, or rating$-$per$-$dollar?

Solution:

$($b$)$ Show that your greedy choice would always yield an optimal solution for that problem. Start

with defining $S_k$ to be a subproblem of the Tatte problem, and let $A_k$ be an optimal solution to

$S_k.$

Solution: