PLEASE SOLVE Q3 NOT Q2.

PLEASE SOLVE Q3 NOT Q2.

PLEASE SOLVE Q3 NOT Q2.

2. Consider the following items with their corresponding weights and values. ltem Weight Value 20 15 10 45 4 2 5 ti Assume you need to carry the items by a truck which can carry at most W-8 tons and only one trip is allowed. a. Set up a recurrence relation for this problem to find the optimal solution b. Find the best solution by creating dynamic programming table. c. What is the time complexity of the dynamic programming algorithm if you have n items and W capacity? Please explain. Consider the problem 2 above. This time, you are allowed to carry partial amounts of the items. Using the same table above, answer the followings. 3. Suggest an efficient greedy algorithm to decide which items we should carry so that you get the most value. What is the complexity of your algorithm? a. b. c.Apply your algorithm to the items above and find the best solution