Part 1) Show, by means of a counterexample, that the following \"greedy\" strate
ID: 3711668 • Letter: P
Question
Part 1) Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density ?of a rod of length i to be p(i) /i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 <= i <= n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.
Part 2)? Consider a modification of the rod-cutting problem (part 1) in which, in addition to a price p(i), for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
Explanation / Answer
Part 1 : Answer
*******************
By the following counterexample we can prove that greedy algorithm Strategy does not always determine an optimal way to cut rods.
=> Let p1 = 1, p2 = 20, p3 = 33, p4 = 36.
=> Let the length of the given rod be 4 inches.
=> According to the Greedy algorithm we run, we first cut the rod of length 3 whose density is maximum.
=> As a result,the total price of the rod is 34.
=> The optimal way is to cut it into two rods of length 2 each fetching us the total price would be 40
=> Hence we proved by an counterexample that the greedy algorithm does not always produce an optimal solution to cut a rods.
Part2 : Dynamic-programming algorithm to solve this modified problem.
*********************************************************************
CutRod(n, P, c)
Define R[1..n] array
Define S[1..n] array //Array to save left-piece lengths
for size = 1 to n //for every length rod find out its optimal revenue
max = P[size] //lines 5-9: compute rsize =max{psize, ???????????????????????( ???? + ????????????? ? ??)
for i = 1 to size-1 //i is the length of the left piece
if (max < P[i] + R[size-i] - c)
max = P[i] +R[size-i] - c
S[size] = i //Save the i that gave the max revenue
R[size] = max //Register the optimal revenue for size-length rod
return R[n]
=> We need to account for cost c on every iteration of the loop in lines 5-6.
=> The major modification required is in the body of the inner for loop, which now reads max = P[i] +R[size-i] - c
=> Whereeas, This change reflects the fixed cost of making the cut, which is deducted from the revenue.
=> Hence, The revenue that is obtained by making a cut is computed as:
price of the left piece + max revenue of the remainder – cost of the cut.
=> Hence we need to consider the option of “not cutting at all” does not incur any c-cost,
it is taken out of the max computing loop – the revenue in this case is simply the price of the piece
=> This means that we do not need to define R[0]=0 fictitious revenue.
=> If we did not make these modifications, then in the case of no cuts, we need to deduct c from the total revenue.