In class, we studied the [0, 1]-knapsack problem. In this assignment you have to explain how to solve the {0, 1}-knapsack problem using dynamic programming. You are given n objects which cannot be broken into smaller pieces. Moreover, you have only 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. Write a recursion for the optimal solution and explain why it is correct. Make sure you define the notation you are using.

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