Problem $2.$ You are given $n$ items, each with a weight $w_i$ and a value $v_i.$ Your goal is

to fill a knapsack of capacity $W$ to maximize the total value. Unlike the discrete $(\frac{0}{1})$

knapsack problem, in which you must take whole items $($a classic dynamic programming

problem that you can try for extra practice$),$ you can now take fractions of items.

a$)(10$ points$)$ Write a greedy algorithm $($in pseudocode$)$ that will select items to max$-$

imize the total value of the knapsack. Explain how your algorithm works.

b$)(10$ points$)$ Prove that your proposed greedy algorithm provides an optimal solution.

You may assume that the ratio $\frac{v_i}{w_i}$ is distinct for each item.

c$)(10$ points$)$ How does this problem differ from the $\frac{0}{1}$ knapsack problem, and why

does the greedy strategy fail for the $\frac{0}{1}$ case? $($Hint: consider how taking a fractional

amount of an item in the fractional knapsack problem might benefit the greedy

approach, but is not allowed in the $\frac{0}{1}$ knapsack problem.$)$