confusion about rod cutting algorithm - dynamic programming

1
votes

I recently saw a rod cutting problem, where B(i) = optimal price for cutting a rod of length i units and p(i) = price of a rod of length i units.

The algorithm given is something like this: B(i) = max(1<=k<=i) {p(k) + B(i-k)}

Shouldn't it be something like this: B(i) = max(1<=k<=floor(i/2)) {B(k) + B(i-k)}
where B(1) = p(1);

so that both parts 've the optimal cost instead of cost for a single rod for one part and optimal cost for the second part.

for example: B(4) = max{ (B(1) + B(3)); (B(2) + B(2)) }

instead of max{ (p(1) + B(3)); (p(2) + B(2)); (p(3) + B(1)) }

Can someone please explain this?

3
algorithmdynamic-programming
It isn't clear what the relationship between p & B are (semantically, not mathematically), but the original algorithm seems to assume p is provided and not determined from B. As your proposal ignores p completely, I'm guessing it doesn't produce the same result. – Scott Hunter
@Scott Hunter yeah, p is given which is cost of rod of some length – athena

3 Answers

3
votes

Actually the formula is correct. You have B(i) = max(1<=k<=i) {p(k) + B(i-k)}. Let's assume you have a rope of length i. If you are to cut it then you will cut a piece of length k where k is between 1 and i and will go on cutting the remaining part of the rope. So overall it costs you p(k)(price to cut the initial part that you decided you will not cut anymore) and the price to cut the remaining B(i-k). This is precisely what the formula does.

Your solution will also do the job but it has a slight drawback - the solution for each subproblem depends on the solution of two(instead of one) simpler subproblems. I believe because of that it will perform worse on the average. Of course having a subproblem depend on several simpler problems is not forbidden or wrong.

2
votes

Let us assume that the optimal price of the rod of length i will be obtained by cutting the rod into p parts of length l1, l2, .., lp such that i= l1+ l2 +..+ lp and l1<l2<l3<…<lp (for simplicity).

There exists a rod piece of length l1 in the optimal solution means that if the rod piece of length l1 is further broken into smaller pieces, then the price of the rod piece of length l1 will decrease. Hence for a rod piece of length l1, we can say that b[l1] = p[l1]. Similarly we have established, b[l2] = p[l2], b[l3]= p[l3], ….., b[lp]= p[lp]. => b(i) = b(l1) + b(l2) +..+ b(lp) is optimal………………..Condition 1

Now consider the case of rod of length l1+l2. The claim is b(l1+l2) = b(l1) + b(l2) is optimal. Let us assume it is not the case. There exists an L such that b(l1+l2) = b(L) + b(l1+l2-L) is optimal. It means that there exists rods of length L and (l1+l2-L) such that:

  • b(L) + b(l1+l2-L)>b(l1)+b(l2).
  • => b(l1) + b(l2) + b(l3) +..+ b(lp) < b(L) + b(l1+l2-L) +b(l3) +…+ b(lp).
  • => Which is a contradiction { See Condition 1}
  • => b(l1+l2) = b(l1) + b(l2) is optimal
  • => Similarly b(l2+l3+l4) = b(l2) + b(l3) + b(l4) is optimal and so on.

Now we have a recurrence b(i) = b(k) + b(i-k) for 1<=k<i.

  • For k=l1, b(i) = b(l1) + b(i-l1) = p[l1] + b(i-l1).
  • For k=l1+l2, b(i) = b(l1+l2) + b(i-l1-l2)
    • = b(l1+l2) + b(l3 + l4 +…+lp)
    • = [b(l1) + b(l2)] + b(l3 + l4 +…+lp)
    • = b(l1) + [b(l2) + b(l3 + l4 +…+lp)]
    • = b(l1) + b(l2+l3+l4+…+lp)
    • = b(l1) + b(i-l1)
    • = p[l1] + b(i-l1)
  • Or for k= l1+l2, b(i) = p[k’] + b(i-k’) where k’=l1.

So to conclude, if we want to find optimal solution of a rod of length i, we try to break the rod of length i into 2 parts of length (l1+l2) and (i-l1+l2) and then we recursively find optimal solutions of the two rod pieces, we end up finding an optimal rod piece of length l1 and optimal solution of rod of length i-l1. Thus we can say:

b(i) = b(k) + b(i-k ) = p[k’] + b(i-k’) for 1<=k,k’<i.

1
votes

The formula is correct. I think the confusion arises when we think of both formulas to be replacement of the other.
Though they count the same phenomena, it is done in two different ways:

Let, B(i) = optimal price for cutting a rod of length i units and p(i) = price of a rod of length i units.

Formula 1: B(i) = max(1<=k<=floor(i/2)) {B(k) + B(i-k)} and P(i)

Formula 2: B(i) = max(1<=k<=i) {p(k) + B(i-k)})

Consider a rod of length 4, it can be cut in the following ways :

1) uncut of length 4

2) 3, 1

3) 2, 2

4) 2, 1, 1

5) 1, 3

6) 1, 2, 1

7) 1, 1, 2

8) 1, 1, 1, 1

According to Formula 1:

option 1 corresponds to P(4)

option 2,5,6,7,8 corresponds to B(1) + B(3)

option 3,4,6,7,8 corresponds to B(2) + B(2)

According to Formula 2:

option 1 corresponds to P(4)

option 2 corresponds to P(3) + B(1)

option 3,4 corresponds to P(2) + B(2)

option 5,6,7,8 corresponds to P(1) + B(3)

So to conclude, 1 and 2 are counting the optimal solution but in different ways, where 2 is more compact and makes lesser recursive calls compared to 1.