Description
CMSC 401- Algorithm Analysis with
Advanced Data Structures
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:
10
4
1
5
7
9
• The size of the rod, N, in the first line. N>=2, N<=100
• The number of cutting points, M, in the second line. M>=1, M<=N-1
• The location of each of M distinct cutting points (will be >0 and <N)
– Only integer values
0 1 2 3 4 5 6 7 8 9 10
Cutting points
Example
Input in correct format
Correct output
23
An order of cutting points that gives the min
cost is 5,1,7,9 (there are also others giving
the same minimum)
10
4
1
5
7
9
0 1 2 3 4 5 6 7 8 9 10
Cutting points 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
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
Submission
• Date due: Thursday, Dec 6th, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
4_FamilyName_FirstName.zip containing
• Java source code in a single file cmsc401.java (all lower case
letters!)
• The file should have your name in a comment in the first line
• Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
• Use standard I/O to read input (System.in, System.out) and output
• Make sure the program compiles and WORKS!
• Late submissions are accepted up to 2 days!
