- 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
- Cutting at 5: 10
- 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
Reviews
There are no reviews yet.