Consider the 0–1 knapsack problem, in which each item has a weight Wi and a value vi, a solution is a subset of the items with total weight at most equal to the capacity W, and the quality of any solution is the sum of the values of the selected items. i 1 2 3 4
Vi 1 4 3 5
Wi 5 4 6 3.
(a) [10 points] Please use dynamic programming to find out what is the optimal solution with W=10, and what are the corresponding selected items.
(b) [6 points] Suppose one greedy algorithm chooses items in descending sorted order by V;/Wi until there is no room for any more items, what is the solution value found by the greedy heuristic for the above 0-1 knapsack problem?