t you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem ....

Transcribed Image Text:

t you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem . In the Rod Cutting problem, you are given an integer n21, along with a sequence of positive prices, P₁ P2. Pn. where p, is the market price of a rod of length i. The goal is to figure out a best way of cutting the given rod of length n to generate the maximum revenue. You can assume that the given prices P1.p2... Pn are all integers. Input The input has the following format. The input starts with n. Then, P₁, P2P₁ follow, one per each line. Output In the first line, output the maximum revenue (rn), followed by an enter key. In the second line, sequentially output the length of each piece in your optimal cutting, followed by a space key. The second line must end by -1 and an enter key. Examples of input and output Input 7 1 5 8 9 10 17 17 Output 18 16-1 The following is the output with white characters shown. 18(enter) 1 (space)6 (space)-1 (enter) Alternatively, the second line can be replaced with "6 1-1", "2 23-1","2 3 2 -1", or "3 2 2-1". That is, any sequence of piece lengths giving the maximum revenue will be considered to t you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem . In the Rod Cutting problem, you are given an integer n21, along with a sequence of positive prices, P₁ P2. Pn. where p, is the market price of a rod of length i. The goal is to figure out a best way of cutting the given rod of length n to generate the maximum revenue. You can assume that the given prices P1.p2... Pn are all integers. Input The input has the following format. The input starts with n. Then, P₁, P2P₁ follow, one per each line. Output In the first line, output the maximum revenue (rn), followed by an enter key. In the second line, sequentially output the length of each piece in your optimal cutting, followed by a space key. The second line must end by -1 and an enter key. Examples of input and output Input 7 1 5 8 9 10 17 17 Output 18 16-1 The following is the output with white characters shown. 18(enter) 1 (space)6 (space)-1 (enter) Alternatively, the second line can be replaced with "6 1-1", "2 23-1","2 3 2 -1", or "3 2 2-1". That is, any sequence of piece lengths giving the maximum revenue will be considered to