The 0-1 knapsack problem. Given six items {(vi, ui)) for i = 1, 2, , 6 as follows: Ui 40 100 50 45 20 10 18 10 2 6 and the total weight W = 100, where vi and wi are the value and weight of item i, respectively. (o) Find the greedy solutions by (1) Greedy by value, i.e., at each step select from the remaining items the one with the highest value (2) Greedy by weight, i.e., at each step select from the remaining items the one with the least weight. (3) Greedy by value density, .e., at each step select from the remaining items with the largest value per pound ratio v/w Are these greedy solutions optimal? Comment your findings (b) Solve the preceding 0-1 knapsack problem by using dynamic programming and comment your findings