Problem 3 (40 points) Alex and Maya have unearthed antique items in Paradise island. They each have a

Knapsack that they can use for carrying the items. Each item has a weight , and their bags have

capacities 1 and 2. Alex will take his Knapsack to the US, where he can sell the item at a

price of . Maya will take her bag to Canada, where the -th item will be sold for a price of .

Their goal is to make the most money, given the limited capacity of their Knapsaks. Let 1 and 2

be the set of items in Alex and Mayas Knapsacks. Formally, their goal is to maximize ( the sum is shown in the image with the full description)

3.1 For any 1 [0,1] and 2 [0,2] let OPT(, 1, 2) be the maximum value they can get only

using the first items and Knapsacks of capacity 1 and 2. Give a recurrence to compute

OPT(, 1, 2) from the values of OPT for smaller sub-problems, and write the base case(s) for

this recurrence. Write a few sentences explaining why your recurrence is correct.

3.2 Using your recurrence, design a dynamic programming algorithm to output the optimal

1 and 2. You may use either a top-down or bottom-up approach. Remember that your

algorithm needs to output the optimal solution, not only its value.

3.3 Analyze the running time of your algorithm.

3 (40 points) Alex and Maya have unearthed n antique items in Paradise island. They each have a Knapsack that they can use for carrying the items. Each item has a weight wi, and their bags have capacities T1 and T2. Alex will take his Knapsack to the US, where he can sell the ith item at a price of pi. Maya will take her bag to Canada, where the i-th item will be sold for a price of qi. Their goal is to make the most money, given the limited capacity of their Knapsaks. Let O1 and O2 be the set of items in Alex and Maya's Knapsacks. Formally, their goal is to maximize iO1pi+iO2qi Subject to iO1wiT1 and iO2wiT2. Help Alex and Maya in finding the optimal solution to their problem. 3.1 For any S1[0,T1] and S2[0,T2] let OPT( i,S1,S2) be the maximum value they can get only using the first i items and Knapsacks of capacity S1 and S2. Give a recurrence to compute OPT(i,S1,S2) from the values of OPT for smaller sub-problems, and write the base case(s) for this recurrence. Write a few sentences explaining why your recurrence is correct. 3.2 Using your recurrence, design a dynamic programming algorithm to output the optimal O1 and O2. You may use either a top-down or bottom-up approach. Remember that your algorithm needs to output the optimal solution, not only its value. 3.3 Analyze the running time of your algorithm