Write a program cmsc401.java that reads the size of the rod and cutting points in the...

    

Transcribed Image Text:

Write a program cmsc401.java that reads the size of the rod and cutting points in the format below: The size of the rod, N, in the first line. N>=2, N =1, M 0 and You are given a rod that is N inches long and a set of M cutting points on the rod. You will need to cut the rod from these M points. You can perform the cuts in any order of these points. After a cut, rod gets divided into two smaller sub- rods. The cost of making a cut is the length of the current sub-rod in which you are making a cut on. Your goal is to minimize the total cost of cutting. Output will show only the minimum cost. Activat Go to Set Input in correct format 10 4 1 5 7 9 Order 1) Cutting at 5: 2) Cutting at 1: 3) Cutting at 7: 4) Cutting at 9: Total Cost: Example Cost 10 5 5 3 0 1 2 3 4 5 6 7 8 9 10 23 Correct output 23 I Cutting points An order of cutting points that gives the min cost is 5,1,7,9 (there are also others giving the same minimum, e.g., 5,7,9,1) Bad cut example: Cutting in the order of 1,5,7,9 which has cost 10+9+5+3=27. Define the problem in terms of cutting the rod from one cutting point to another one - C(i,j) = cost of cutting the rod from point i to point j Find the recursive formula Apply a dynamic programming method Algorithm should have O(M) complexity - M: number of cutting points - Complexity should not depend on N, the length of rod. Activ Write a program cmsc401.java that reads the size of the rod and cutting points in the format below: The size of the rod, N, in the first line. N>=2, N =1, M 0 and You are given a rod that is N inches long and a set of M cutting points on the rod. You will need to cut the rod from these M points. You can perform the cuts in any order of these points. After a cut, rod gets divided into two smaller sub- rods. The cost of making a cut is the length of the current sub-rod in which you are making a cut on. Your goal is to minimize the total cost of cutting. Output will show only the minimum cost. Activat Go to Set Input in correct format 10 4 1 5 7 9 Order 1) Cutting at 5: 2) Cutting at 1: 3) Cutting at 7: 4) Cutting at 9: Total Cost: Example Cost 10 5 5 3 0 1 2 3 4 5 6 7 8 9 10 23 Correct output 23 I Cutting points An order of cutting points that gives the min cost is 5,1,7,9 (there are also others giving the same minimum, e.g., 5,7,9,1) Bad cut example: Cutting in the order of 1,5,7,9 which has cost 10+9+5+3=27. Define the problem in terms of cutting the rod from one cutting point to another one - C(i,j) = cost of cutting the rod from point i to point j Find the recursive formula Apply a dynamic programming method Algorithm should have O(M) complexity - M: number of cutting points - Complexity should not depend on N, the length of rod. Activ