java

The class RodCutter should contain a public method -- public static int[] getOptCutSizes (int rodSize, int[] prices)

The method should return an int array with the total maximum sales amount achievable followed by the rod sizes (sorted by increasing size) used to achieve the maximum amount. In some cases where the solution is not be unique, any correct solution is acceptable.

just write the above RodCutter class, no need to answer the questions

3. Rod Cutting: Design a dynamic programming algorithm for the following problem. Find the maximum total sale price, MTSP, 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. Examples Rod Length 4, p1 = 2, p2 = 4, p = 7,24 = 8 then MTSP=9, use lengths (1,3) Rod Length 4, p1 = 3, p2 = 7, p3 = 9, p4 = 12 then MTSP = 14, use lengths (2, 2) Rod Length 4, p1 = 2, p2 = 4,23 = 7,24 = 11 then MTSP = 11, use lengths (4) Rod Length 4, p = 3, P2 = 5, P3 = 8,24 = 11 then MTSP-12, use lengths (1,1,1,1) The following is a rough guide to the thought process (not to be submitted) you should follow: 1. Write an English description of MTSP (k) 2. Write a recurrence relation for the objective function: MTSP (k) = some function involving smaller versions of the problem. Specify the base case. This specifies the optimal substructure of the problem. 3. Specify the table you will use to keep track of the MTSP(k)? 4. Write pseudo code fragments to fill in the table and to trace back using the table to find the rod sizes that give you the optimal solution. 3. Rod Cutting: Design a dynamic programming algorithm for the following problem. Find the maximum total sale price, MTSP, 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. Examples Rod Length 4, p1 = 2, p2 = 4, p = 7,24 = 8 then MTSP=9, use lengths (1,3) Rod Length 4, p1 = 3, p2 = 7, p3 = 9, p4 = 12 then MTSP = 14, use lengths (2, 2) Rod Length 4, p1 = 2, p2 = 4,23 = 7,24 = 11 then MTSP = 11, use lengths (4) Rod Length 4, p = 3, P2 = 5, P3 = 8,24 = 11 then MTSP-12, use lengths (1,1,1,1) The following is a rough guide to the thought process (not to be submitted) you should follow: 1. Write an English description of MTSP (k) 2. Write a recurrence relation for the objective function: MTSP (k) = some function involving smaller versions of the problem. Specify the base case. This specifies the optimal substructure of the problem. 3. Specify the table you will use to keep track of the MTSP(k)? 4. Write pseudo code fragments to fill in the table and to trace back using the table to find the rod sizes that give you the optimal solution