In class, we studied the fractional [0, 1]-knapsack problem using a greedy approach. In this assignment, we work on the {0, 1}-knapsack problem using dynamic programming.

You are given n objects which cannot be broken into smaller pieces. Moreover, you have exactly one copy of each object. Each object i (where 1 i n) has weight wi > 0 and value vi > 0. You have a knapsack that can carry a total weight not exceeding W. Your goal is to fill the knapsack in a way that maximizes the total value of the included objects, while respecting the capacity constraint. For each object i (where 1 i n), either you bring it or not.

1. (10 marks) Let opt[i, j] be the maximum value of the objects we can carry if the weight limit is j and we are only allowed to include objects numbered from 1 to i. Fill the gaps in the following recursion defined for all 0 i n and all 0 j W.

opt[i, j] = _______ if i = 0, _______ if j = 0, _______ if j wi, i != 0 and j != 0, _______ otherwise.

Note: no justification.

2. (10 marks) Consider the following input and fill the table corresponding to the recursion you found in #1: n = 6, w1 = 1, w2 = 3, w3 = 2, w4 = 5, w5 = 4, w6 = 7, v1 = 2, v2 = 3, v3 = 5, v4 = 7, v5 = 11, v6 = 13 and W = 10. Moreover, give all optimal solutions.

Note: no justification.