[SOLVED] CMSC401-Assignment 4

Description

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.
• 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