Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
a. Correctness of dynamic programming algorithm: Usually, a dynamic programming algorithm can be seen as a recursion and proof by induction is one of the easiest way to show its correctness. The structure of a proof by strong induction for one variable, say n, contains three parts. First, we define the Proposition P(n) that we want to prove for the variable n. Next, we show that the proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive step, we assume that P(n) holds for any value of n strictly smaller than n' , then we prove that P(n') also holds. Use the proof by strong induction properly to show that the algorithm of the Knapsack problem above is correct.

a. Correctness of dynamic programming algorithm: Usually, a dynamic programming algorithm can be seen as a recursion and proof by induction is one of the easiest way to show its correctness. The structure of a proof by strong induction for one variable, say n, contains three parts. First, we define the Proposition P(n) that we want to prove for the variable n. Next, we show that the proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive step, we assume that P(n) holds for any value of n strictly smaller than n' , then we prove that P(n') also holds. Use the proof by strong induction properly to show that the algorithm of the Knapsack problem above is correct.

icon
Related questions
Question

a. Correctness of dynamic programming algorithm:

Usually, a dynamic programming algorithm can be seen as a recursion and proof by induction is one of the easiest way to show its correctness. The structure of a proof by strong induction for one variable, say n, contains three parts. First, we define the Proposition P(n) that we want to prove for the variable n. Next, we show that the proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive step, we assume that P(n) holds for any value of n strictly smaller than n' , then we prove that P(n') also holds.

Use the proof by strong induction properly to show that the algorithm of the Knapsack problem above is correct. 

 

b. Bounded Knapsack Problem:

Let us consider a similar problem, in which each item i has ci > 0 copies (ci is an integer). Thus, xi is no longer a binary value, but a non-negative integer at most equal to ci , 0 ≤ xi ≤ ci . Modify the dynamic programming algorithm seen at class for this problem.

Note: One could consider a new set, in which item i has ci occurrences. Then, the algorithm seen as class can be applied. However, this could be costly since ci might be large. Therefore, the algorithm you propose should be different than this one. 

 

c. Unbounded Knapsack Problem:

In this question, we consider the case where the quantity of each item is unlimited. Thus, xi could be any non-negative integer. Provide a dynamic programming algorithm for this problem.

Knapsack Problem. Let n > 0 be the number of distinct items and W > 0 be the knapsack capacity. For each item i, w; > 0 denotes the item weight and v; > 0 denotes its value. The goal is to maximize the total value while n OPT(i, w) = OPT(i-1, w) OPTI i=1 Vi i n Σ wix; ≤ W i=1 where x₂ = {0, 1} for i € {1, …, n}. Algorithm. We recall the recursive form of the dynamic programming algorithm. Let OPT (i, w) be the maximum profit subset of items 1, . ,i with weight limit w. If OPT does not select the item i, then OPT selects among items {1,. i-1} with weight limit w. Otherwise, OPT selects among items {1,..., i – 1} with weight limit w. We could formalize as 2..." max{OPT(i — 1, w), v; + OPT(i — 1, w — w;)} - if i = 0 if w; > w otherwise
Transcribed Image Text:Knapsack Problem. Let n > 0 be the number of distinct items and W > 0 be the knapsack capacity. For each item i, w; > 0 denotes the item weight and v; > 0 denotes its value. The goal is to maximize the total value while n OPT(i, w) = OPT(i-1, w) OPTI i=1 Vi i n Σ wix; ≤ W i=1 where x₂ = {0, 1} for i € {1, …, n}. Algorithm. We recall the recursive form of the dynamic programming algorithm. Let OPT (i, w) be the maximum profit subset of items 1, . ,i with weight limit w. If OPT does not select the item i, then OPT selects among items {1,. i-1} with weight limit w. Otherwise, OPT selects among items {1,..., i – 1} with weight limit w. We could formalize as 2..." max{OPT(i — 1, w), v; + OPT(i — 1, w — w;)} - if i = 0 if w; > w otherwise
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer