Question

Rod-cutting problem Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be obtained by cutting a rod of n units long into integer-length pieces if the sale price of a piece i units long is pi for i = 1, 2, . . . , n. What are the time and space efficiencies of your algorithm?

Answer 1

The answer is 5:11

Step-by-step explanation:

pi for i = 1,2...,n

Considering, rod of length: 4 ways to sell:

selling length : 4 (no cuts), price: 9

selling length: 1,1,1,1 (3 cuts), price: 4

Best price for rod of length= 4:10

n-1 = 2 ⁿ⁻¹

0(2^n-1

(length⇒ 0); return ≤ -1; (int i=0; i≤ length; i ++)

max= Math.max(max, value[i] + profit(value, length - (i+1))); return max;} public static void main (String [] args {int [] value = {2,3,7,8,9} ; int len= 5; ("Max profit for length is"+ len + ":" + profit(value, len)); Max profit for length is 5:11