4. 0-1 Knapsack Problem. Suppose there exists a set A of n items; and that item...

 

Transcribed Image Text:

4. 0-1 Knapsack Problem. Suppose there exists a set A of n items; and that item a has weight w(a) and value v(a). Given budget B, the knapsack problem is to select a subset B of items such that bB w(b) B and EB (b) is maximized. (a) Give a dynamic programming solution for this problem. As part of your solution, describe (and prove) the optimal substructure of the problem. (b) Can you formulate a greedy algorithm for this problem? Justify your answer. 4. 0-1 Knapsack Problem. Suppose there exists a set A of n items; and that item a has weight w(a) and value v(a). Given budget B, the knapsack problem is to select a subset B of items such that bB w(b) B and EB (b) is maximized. (a) Give a dynamic programming solution for this problem. As part of your solution, describe (and prove) the optimal substructure of the problem. (b) Can you formulate a greedy algorithm for this problem? Justify your answer.