• 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 ¹⁰₄
• 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) 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(M³) complexity