• 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