Minimum Cost Rod Cutting
• 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 subrods.
• The cost of making a cut is the length of the current sub-rod in which you are making a cut.
• Your goal is to minimize the total cost of cutting.
• Output will show only the minimum cost.
Assignment 4
• 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<=100 104
• The number of cutting points, M, in the second line. M>=1, M<=N-1 1
• The location of each of M distinct cutting points (will be >0 and <N) 5 – Only integer values 7
9
0 1 2 3 4 5 6 7 8 9 10
Cutting points
Example
Input in correct format Correct output
23
10
4
1 0 1 2 3 4 5 6 7 8 9 10
5
7
9
Order Cost
1) Cutting at 5: 10
2) Cutting at 1: 5 3) Cutting at 7: 5
4) Cutting at 9: 3
---------------------------------
Total Cost: 23
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)
Hint
• Define the problem in terms of cutting the rod from one 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
• Target O(M3) complexity
