[Solved]Dynamic Program Algorithms 0 1 Knapsack Problem 10 Pts Given Weights Wo W Wn 1 Provisions Q37109086
Analysis of algorithms
Dynamic Program Algorithms The 0 – 1 knapsack problem (10 pts) Given weights (wo, w,…, wn-1) of provisions and their profits(po, pi, . . . , pn-1), a knapsack capacity C, and a bit vector 〈bo, by, . .. , b”-1), which specifies whether or not a provision is or is not in the knapsack. For 0 m < and 0 S j< n, define P(j, m) to be the profit of the optimal solution to the 0 – 1 knapsack problem using provisions o, …j and knapsack capacity m Explain the how these recurrences are helpful in framing a solu- tion to the problem. P(j, m) = P(j-1, m) if wi > m P(j m) max P(j-1, m), Pi +P(j-1, m-) if w Sm and the initial conditions PO,m) Po if woleqm P(0, m) = 0 ifa0 > m Let T(n) be the time complexity to calculate P(n – 1, m) recur- sively. Argue that the time complexity is modeled by the recurrence T(n) -2(n -1) + c, solve this recurrence, and describe the rate of growth. Consider an instance of the 0- 1 knapsack problem with 6 pro- visions that have weights: 2, 3, 5, 8, 13, and 16. With corresponding profits 1, 2, 3, 5, 7, and 10, And a knapsack capacity C 30. 1. (5 pts) Show how to use the recurrences to fill the missing values in a dynamic programming table below 0 1 2 3 4 5 …30 2. (5 pts) Given n, the number of provisions and C the knapsack capacity, what is the time complexity to complete the table and solve an instance of the problem Answer 3. (5 pts) Explain why this dynamic programming approach does not lead to a polynomial-time algorithm for the 0- 1 knapsack problem. (Hint: the capacity C could be exponentially large in n) 4 (5 pts) it can be shown that the 0 1 knapsack problem is NP complete What does this mean? Show transcribed image text Dynamic Program Algorithms The 0 – 1 knapsack problem (10 pts) Given weights (wo, w,…, wn-1) of provisions and their profits(po, pi, . . . , pn-1), a knapsack capacity C, and a bit vector 〈bo, by, . .. , b”-1), which specifies whether or not a provision is or is not in the knapsack. For 0 m m Let T(n) be the time complexity to calculate P(n – 1, m) recur- sively. Argue that the time complexity is modeled by the recurrence T(n) -2(n -1) + c, solve this recurrence, and describe the rate of growth. Consider an instance of the 0- 1 knapsack problem with 6 pro- visions that have weights: 2, 3, 5, 8, 13, and 16. With corresponding profits 1, 2, 3, 5, 7, and 10, And a knapsack capacity C 30. 1. (5 pts) Show how to use the recurrences to fill the missing values in a dynamic programming table below 0 1 2 3 4 5 …30 2. (5 pts) Given n, the number of provisions and C the knapsack capacity, what is the time complexity to complete the table and solve an instance of the problem Answer
3. (5 pts) Explain why this dynamic programming approach does not lead to a polynomial-time algorithm for the 0- 1 knapsack problem. (Hint: the capacity C could be exponentially large in n) 4 (5 pts) it can be shown that the 0 1 knapsack problem is NP complete What does this mean?
Expert Answer
Answer to Dynamic Program Algorithms The 0 – 1 knapsack problem (10 pts) Given weights (wo, w,…, wn-1) of provisions and their … . . .
OR
