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 an integer weight wi > 0 and a 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 = 2, w3 = 3, w4 = 2, w5 = 5, w6 = 4, v1 = 17, v2 = 2, v3 = 1, v4 = 1, v5 = 18, v6 = 11 and W = 12. Moreover, give all optimal solutions.
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 an integer weight wi > 0 and a 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 = 2, w3 = 3, w4 = 2, w5 = 5, w6 = 4, v1 = 17, v2 = 2, v3 = 1, v4 = 1, v5 = 18, v6 = 11 and W = 12. Moreover, give all optimal solutions.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
