Let's consider the bar cutting problem: Suppose we have a bar of length n. p is the selling price of a bar of length i; Let's assume that (i=1, 2, ..., n). Our goal is to split the bar into parts of integer length to get maximum profit. (a) Design a dynamic programming algorithm for this problem. Instead of pseudocode, a well-explained explanation is preferred. Also mention the time and place complexity of your algorithm. (Hint: Define the function F(n) as the maximum profit that can be obtained for a stick of length n and construct an iterative relation.) (b) Apply the dynamic programming algorithm you designed for the following example: You have a stick of length 6. Selling prices of parts: pi=1, P2=6, p3=7, p=11, p=14, po=15.
Let's consider the bar cutting problem: Suppose we have a bar of length n. p is the selling price of a bar of length i; Let's assume that (i=1, 2, ..., n). Our goal is to split the bar into parts of integer length to get maximum profit.
(a) Design a dynamic
(b) Apply the dynamic programming algorithm you designed for the following example: You have a stick of length 6. Selling prices of parts: pi=1, P2=6, p3=7, p=11, p=14, po=15.
Step by step
Solved in 2 steps