confusion about rod cutting algorithm - dynamic pr

问题:

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?

回答1:

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:

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.