Question

Prove that your algorithm works!

6.) Dynamic Consider a modification of the rod-cutting problem in which, in addition to a price p, 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. Prove that your algorithm works.

Answer 1

Proof: by tracing the above algorithm for some input data we can understand the working .

Length i	1	2	3	4	5	6	7	8
Price pi	1	5	8	9	10	17	17	20

n = 9 , c = 2

if p,n,c are we passed to our algorithm.

r[0..n], s[0..n] two arrays

r[0] = 0

for j=1

                q= p[j]

                inner loop i = 1 to j-1

                                here j-1 is 0 so loop break;

for j=2

                q= p[j]

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 5 < 1 + 1 – 2 is false so we don’t cut here

                still now we store r[0]=0,r[1]=1,r[2]=5 there are optimal only.

for j=3

                q= p[j] = 8

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 8 < 1 + 5 – 2 is false so we don’t cut here

                                q <p[2] + p[1] – c means 8 < 5 + 1 -2 is false so we don’t cut here

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 there are optimal only.

for j=4

                q= p[j] = 9

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 9 < 1 + 8 – 2 is false so we don’t cut here

                                q <p[2] + p[2] – c means 9 < 5 + 5 -2 is false so we don’t cut here

                                q <p[3] + p[1] – c means 9 < 8 + 1 -2 is false so we don’t cut here

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 r[4]=9

for j=5

                q= p[j] = 10

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 10 < 1 + 9 – 2 is false so we don’t cut here

                                q <p[2] + p[3] – c means 10 < 5 + 8 -2 is true so we cut here.

                                q = 5 + 8 -2 = 11

s[j] = i // adding the split where we did cutting.

                                q <p[3] + p[2] – c means 11 < 8 + 5 -2 is false so we don’t cut here

                                q <p[4] + p[1] – c means 11 < 9 + 1 -2 is false so we don’t cut here

r[5] =11

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 r[4]=9 r[5] =11

for j=6

                q= p[j] = 17

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 17 < 1 + 11 – 2 is false so we don’t cut here

                                q <p[2] + p[4] – c means 17 < 5 + 9 -2 is false.

                                q <p[3] + p[3] – c means 17 < 8 + 8 -2 is false so we don’t cut here

                                q <p[4] + p[2] – c means 17 < 9 + 5 -2 is false so we don’t cut here

                                q <p[5] + p[1] – c means 17 < 11+ 1 -2 is false so we don’t cut here

r[6] =17

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 r[4]=9 r[5] =11 r[6] =17

for j=7

                q= p[j] = 17

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 17 < 1 + 17 – 2 is false so we don’t cut here

                                q <p[2] + p[5] – c means 17 < 5 + 11 -2 is false.

                                q <p[3] + p[4] – c means 17 < 8 + 9 -2 is false so we don’t cut here

                                q <p[4] + p[3] – c means 17 < 9 + 8 -2 is false so we don’t cut here

                                q <p[5] + p[2] – c means 17 < 11+ 5 -2 is false so we don’t cut here

                                q <p[6] + p[1] – c means 17 < 17+ 1 -2 is false so we don’t cut here

r[7] =17

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 r[4]=9 r[5] =11 r[6] =17 r[7]=17

for j=8

                q= p[j] = 20

                inner loop i = 1 to j-1

                                q < p[i] + p[j-i] – c   means 20 < 1 + 17 – 2 is false so we don’t cut here

                                q <p[2] + p[6] – c means 20 < 5 + 17 -2 is false.

                                q <p[3] + p[5] – c means 20 < 8 + 11 -2 is false so we don’t cut here

                                q <p[4] + p[4] – c means 20 < 9 + 9 -2 is false so we don’t cut here

                                q <p[5] + p[3] – c means 20 < 11+ 8 -2 is false so we don’t cut here

                                q <p[6] + p[2] – c means 20 < 17+ 5 -2 is false so we don’t cut here

                                q <p[7] + p[1] – c means 20 < 17+ 1 -2 is false so we don’t cut here

r[8] =20

                still now we store r[0]=0,r[1]=1,r[2]=5 r[3]=8 r[4]=9 r[5] =11 r[6] =17 r[7]=17 r[8] =20

returns r and s now.

In our problem we get profit without cuts only because the cutting cost is more .

if we trace the algorithm with different cut costs we can understand in better way.