(a) Develop a greedy algorithm for the multiple-choice knapsack problem. For full credit, you should first (i) describe the decision faced at each iteration of your algorithm and what constitutes the greedy decision and (ii) describe the subproblem you end up with after making your decision at each iteration. For the knapsack problem, the answer to (i) was you were faced with the decision of which item to try to include next into the knapsack, the greedy decision was to examine item i with the largest vi si and (ii) was a knapsack problem with one less item and, possibly, less remaining capacity. You should provide the pseudocode for the algorithm. In terms of O() notation, provide the time required/number of operations of your algorithm. Hint: In the greedy algorithm for the knapsack problem, we let S represent the set of items remaining in our problem. In the greedy algorithm for the multiple-choice knapsack problem, you could still let S represent the set of items remaining in the problem.

(b) Develop a dynamic programming algorithm for the multiple-choice knapsack problem. You do not need to provide the pseudocode for the algorithm. Provide the state defininitions, the recurrence relationships between the states of your problem, the base case for the recurrence, and determine the time required to solve the dynamic program (i.e., how long will it require to calculate the value functions for all states in our dynamic program.) Hint: you can have the states of the dynamic program be the same for the multiple-choice knapsack problem as for the knapsack problem itself.

(c) Illustrate your method on the following multiple-choice knapsack problem. We have 4 items in the problem, each with 3 variants. The entries of the following table are (vij , sij ), i.e., the entry in the ith row and the jth column represent the value and the size of the j-th variant of item i.

	1	2	3
1	(8, 3)	(5, 2)	(0, 0)
2	(6, 2)	(3, 3)	(0, 0)
3	(10, 5)	(8, 4)	(0, 0)
4	(2, 1)	(3, 2)	(0, 0)

The capacity of the knapsack is C = 6. Be as clear as possible to what your method is doing at each step (for example, tell me what you are selecting in the greedy algorithm or how you are calculating the recurrence relations in the dynamic program).