$(10$ points$)$ Mr E next shows you his Bag of Limited Holding. It can only hold so much, $($b$)$ After a heated argument, he accepts that your example proves his algorithm is

not correct. He now makes you consider the following algorithm for the knapsack

problem. Call the relative value of item i the ratio $va\frac{l_i}{w}{t}_i.$ Consider the greedy

algorithm which, among the remaining items, chooses the item of maximum rel$-$

ative value such that it will not make the total weight exceed the threshold $W.$

Give an example of knapsack where this greedy algorithm fails. Show the order in

which the algorithm selects the items, and also show a higher$-$value subset whose

weight does not exceed the threshold.

so he's trying to maximize the value of the items with which he'll fill his Bag.

$($a$)$ MrE hands you a list of $n$ items, each with a value and weight $(va{l}_i,w{t}_i),$ and a

threshold weight $W.$ All values and weights are strictly positive. He is trying to

select a subset $S$ of the items such that ${\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}w{t}_{i}W$ and maximizing ${\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}va{l}_i$

$($Note that, unlike change$-$making, here there is only one of each item, whereas in

change$-$making you in principle have an unlimited number of each type of coin.$)$

He "patiently" describes the following greedy algorithm: among the remaining

items, choose the item of maximum value such that it will not make the total

weight exceed the threshold $W.$

Give an example of knapsack with at least $5$ items where this greedy algorithm

fails. Show the order in which the algorithm selects the items, and also show a

higher$-$value subset whose weight does not exceed the threshold.