Exercise 6.20 You are given a stick of length n units. Your goal is to cut the stick into different pieces (each piece should be of integer length only) so that the total value of all the pieces is maximized. A piece of length i units has value vi, for i = 1, 2, ..., n. You should design a dynamic programming algorithm that determines the maximum total value that is possible. (i) Consider the sequence of 7 numbers: 2, 3, 4, 5, 6, 7, 9. Let the ith number in the sequence represents the value of piece of length i, i.e., the value of piece of length 1 is 2, of length 2 is 3, length 3 is 4 and so on. What is the best way to cut the pieces for a stick of length 7? What is the maximum value ? (ii) Define the subproblems for your DP solution on a general instance of the problem where the stick is of length n and a piece of length i has value vi. (iii) Give a recursive formulation to solve the subproblems. Don't forget the base cases. (iv) What is the running time of your solution? (v) Write a DP algorithm (give pseudocode) that outputs the maximum value. (vi) Describe an algorithm to output the sizes of the pieces of the cut that corresponds to the maximum value. Exercise 6.20 You are given a stick of length n units. Your goal is to cut the stick into different pieces (each piece should be of integer length only) so that the total value of all the pieces is maximized. A piece of length i units has value vi, for i = 1, 2, ..., n. You should design a dynamic programming algorithm that determines the maximum total value that is possible. (i) Consider the sequence of 7 numbers: 2, 3, 4, 5, 6, 7, 9. Let the ith number in the sequence represents the value of piece of length i, i.e., the value of piece of length 1 is 2, of length 2 is 3, length 3 is 4 and so on. What is the best way to cut the pieces for a stick of length 7? What is the maximum value ? (ii) Define the subproblems for your DP solution on a general instance of the problem where the stick is of length n and a piece of length i has value vi. (iii) Give a recursive formulation to solve the subproblems. Don't forget the base cases. (iv) What is the running time of your solution? (v) Write a DP algorithm (give pseudocode) that outputs the maximum value. (vi) Describe an algorithm to output the sizes of the pieces of the cut that corresponds to the maximum value
