1. You have a long piece of steel bar which you wish to split into a number of s
ID: 3700224 • Letter: 1
Question
1. You have a long piece of steel bar which you wish to split into a number of shorter lengths. The cost of each cut is proportional to the length of the steel bar (say ten dollars per meter). This means that the order in which the cuts are made can make a large difference in the totai cost. For example, suppose you have a 31-meter steel bar, and wish to cut it at points 5, 13, 17 and 24 meters from the left-hand end. If the cuts are made in left-to-right order, the first cuts costs 310 dollars and gives two smaller bars of lengths 5 and 26 meters. The second cut is made in the 26-meter length, and thus costs 260 dollars. The total cost of making the cuts in left-to-right order is then 310+260+180+140 890 dollars. In contrast, if the cuts are made in reverse order, the total cost is 310+240+170+130 850 dollars. The problem can be formalized as follows. Given an integer length x, and the integer cutting points 1n (where 1 S x for 1 SiSn), find the minimum cost of cutting a piece of steel bar of length x at the n points at distance X1.x2 from the left-hand end (given that cutting a piece of bar of length y at any costs 10 x y). Devise a polynomial-time algorithm for the problem using dynamic programming techniques. 2. Write a program (filename: prog7.go) in Go to solve the previous problem. Using the example above, the input data format is as follows: 31 4 5 13 17 24 Your program should firstly read an integer (i.e. 31) which is the total length of the steel bar. Next, your program reads another integer (i.e. 4) which tells your program how many integers followed. Then, your program needs to read the four cutting points.Explanation / Answer
Answer :
Algorithm : FIndmincost(rodlength, cutlist)
//Input: rodLength, length of the rod
cutList, list representing the cut points
//Output: retCost, minimum cost to cut the rod at given points
Add 0 to beginning of the cutList
Add rodLength to the end of the cutList
Set size to length of cutList
cost = long[size] [ size]
idxAry = int[size][size]
for kk = 0 to size-1 do
for aa = 0 to size-1 do
cost[kk][aa] = -1
end for
end for
for kk = 0 to size-2 do
cost[kk][kk+1] = 0
end for
for kk = 2 to size-1 do
for aa = 0 to size-kk-1 do
tp = aa + kk
firstCut = cutList[tp] – cutList[aa]
cost[aa][tp] = cost[aa][aa+1] +cost[aa+1][tp]+firstCut
idxAry[aa][tp] = aa+1
for bb = aa+2 to tp-1 do
newCost – cost[aa][bb] +cost[bb][tp] +firstCut
if newCost <cost[aa][tp]
cost[aa][tp] = newCost
idxAry[aa][tp] = bb
end if
end for
end for
end for
Declare an array called rsltAry.
findSequence(0, size-1, idxAry, rsltAry, cutList)
set retCost to 0
set sze to length of rsltAry
for kk =0 : sze-1
retCost = n*10
n = n – rsltAry[kk]
end for
return retCost
Algorithm: findSequence(I, j, idxAry, rsltAry, B)
//Input: i and j are integer
IdxAry represents two dimensional array
RsltAry represents the sequence
B is the list of cut points
//Output: rsltAry, the sequence
if i>= j-1
return
end if
set lowest to idxAry[i][j]
rsltAry.add(B[lowest])
findSequence(i, lowest, idxAry, rsltAry, B)
findSequence(lowest, j, idxAry, rsltAry, B)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.