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.
11/20/18 2
Assignment 4
• Write a program cmsc401.java that reads the size of the rod
and cutting points in the format below:
11/20/18 3
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
11/20/18 4
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
11/20/18 5
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!
11/20/18 6
