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. 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 if j wi ________otherwise. } 2) 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

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 ezactly one copy of each object. Each objecti (where 1 Si n) has weight w > 0 and value v >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 iSn), either you bring it or not. 1. (10 marks) Let optli, jl be the maxium 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 0i S n and all 0Sj ifi=0, if j-0 opt[i,j] = 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, wi-1, w2-3, tt's-2, u,-5, tv,-4, u's-7, th-2, 2-3,-5,47,, 13 and W 10 Moreover, give all optimal solutions. Note: no justification