To cut a n centimeter long gold bar into two pieces costs $n. When a gold bar is cut into many pieces, the order in which the cuts occur can affect the total amount of costs. For example, to cut a 20 centimeter gold bar at length marks 2, 8, and 10 (numbering the length marks in ascending order from the left-hand end, starting from 1). If the cuts to occur in left-to-right order, then the first cut costs $20, the second cut costs $18 (cutting the remaining 18 centimeter bar at originally length mark 8), and the third cut costs $12, totaling $50. If the cuts to occur in right-to-left order, however, then the first cut costs $20 time, the second cut costs $10, and the third cut costs $8, totaling $38. In yet another order, the first cut is at 8 (costing $20), then the 2nd cut is at 2 (costing $8), and finally the third cut is at 10 (costing $12), for a total cost of $40. Given a n centimeter long gold bar G and an array C[1..m] containing the cutting points in ascending order): (1) Formulate the recursive relation of the optimal solution; (2) Design a bottom-up algorithm (pseudo code) to calculate the lowest cost for a sequence of cuts; (3) Analyze the complexity of your algorithm; (4) Write an algorithm (pseudo code) to print out a sequence of cuts that achieves this cost.
To cut a n centimeter long gold bar into two pieces costs $n. When a gold bar is cut into many
pieces, the order in which the cuts occur can affect the total amount of costs. For example, to cut a
20 centimeter gold bar at length marks 2, 8, and 10 (numbering the length marks in ascending order
from the left-hand end, starting from 1). If the cuts to occur in left-to-right order, then the first cut
costs $20, the second cut costs $18 (cutting the remaining 18 centimeter bar at originally length
mark 8), and the third cut costs $12, totaling $50. If the cuts to occur in right-to-left order, however,
then the first cut costs $20 time, the second cut costs $10, and the third cut costs $8, totaling $38.
In yet another order, the first cut is at 8 (costing $20), then the 2nd cut is at 2 (costing $8), and
finally the third cut is at 10 (costing $12), for a total cost of $40. Given a n centimeter long gold
bar G and an array C[1..m] containing the cutting points in ascending order):
(1) Formulate the recursive relation of the optimal solution;
(2) Design a bottom-up algorithm (pseudo code) to calculate the lowest cost for a sequence of cuts;
(3) Analyze the complexity of your algorithm;
(4) Write an algorithm (pseudo code) to print out a sequence of cuts that achieves this cost.
Step by step
Solved in 5 steps
