Problem $3.$ Tatte Like Latte Part One $(10$ points$)$ Problem $4.$ Tatte Like Latte Part Two $(10$ points$)$

You've eaten your fill of pastries, and now you have a new dollar amount to spend on Tatte's

ground coffee beans. Like before, you've assigned a rating to each type of bean. Each type also has

a price$-$per$-$pound listed, but you don't need to buy an entire pound of beans; instead, you can buy

up to one pound of any type. You can also buy multiple types, as long as you don't go over your

$$D$ limit$.$

For example, here is what the menu might look like now.

$($a$)$ Going by ratings $($largest to smallest$),$ what would a Greedy solution be assuming you have

$$15$ to spend and can purchase up to one pound of any coffee flavor? What would the total

rating be$?$

Solution:

$($b$)$ In some versions of this problem, we compute the ratio of value $($ranking$)$ to weight $($price$),$

as shown in the table below. Using the rating$-$per$-$dollar as the way each item is evaluated,

what would a Greedy solution be assuming you have $$15$ to spend? What would the total

rating be$?$

Solution:

$($c$)$ Give the pseudocode for a greedy solution that would go by either Rating, or Rating$-$per$-$

Dollar, whichever is better based on your solutions above. $($You can assume you have access

to any sorting algorithm we've covered.$)$ Your algorithm should take as parameters: $D,$ the

total dollar amount you can spend, an array of coffee prices, and a corresponding array of

coffee ratings. It should return the total rating of an optimal solution.

Solution: 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:

You have $$D$ to spend on pastries at Tatte. In the bakery display, you see exactly one of each item $-$

each has a price listed next to it$,$ and you've personally assigned a rating of $1-10$ as well. You want

to spend your money in an optimal way, i$.$e$.,$ you want to maximize the sum of ratings on your

items without going over $$D.$

Here are the items you can buy, along with their prices and your individual ratings: