Solving the carpentry problem by dynamic programming

Last week I was discussing about dynamic programming technique with a friend. We were discussing about the carpenter problem given here (http://parasol.tamu.edu/~amato/Courses/311/exam3.review.html - problem 4). The following is an attempt to solve the problem. Comments are welcome. Note: I am not approaching this problem through a mathematical recurrence relation. I am simply trying to solve this problem by plain common sense. However let me make an attempt to write the recurrence relation at the end (atleast let me see how much I remember my B.E classes :-))

At the outset the problem is a divide and conquer problem. The solution is

1. Make the first cut at a point that is near the half way mark. The cost of making this cut is the length of the wood (L)
2. Then we will have two halves with lengths L1 and L2. Apply the step 1 recursively for each of these pieces till we have made the cut at all the marked points.
   

Now to apply dynamic programming to this problem, we have to store the result of each portion calculated. The result shall be stored in the followig way

• A hash table mapping the length L and list of points (a1, a2, ... an) to cut on the wood, as the key, and the cost of making such cuts as the value.

So as we recursively calculate the cost of cutting each piece of wood of length L at points (a1, a2, .. an) store the result in memory. If some other half of the wood has the same length and cutting pattern, then the result is readily available in memory. It need not be cut again.

For example, consider a wood of length 10 metres to be cut at points a1 = 1 metre, a2 = 4 metre, a3 = 6 metre and a4 = 9 metre. Here are the steps.

• Make the first cut at a point near the half way (5 metre mark). In the above example points a2 and a3 are equidistant from centre. So lets choose a2. Now we have two woods of length 4 metre and 6 metre. After this cut the hash table will have an entry.

Value(10#1#4#6#9) = 10 ; Where 10#1#4#6#9 is the key; 10 = length of the wood, 1,4,6,9 are the points at which cut has to be made .

• Now apply the above rule for the two wooden parts we have now. Applying it on the first one, we have

Value(4#1) = 4

• Applying the rule on the second part, we have

Value(6#2#5) = 6 + value(4#3). Note that in the key 6#2#5, 6 = length of the wood, 2 = point of first cut (Point a3 (6 metres) - 4), 5 = point of second cut. This wood of length 6 has to be cut at point closer to its centre. That is the point at 2 metres. The cost of making this cut is 6. Now we have two parts from this cut. The first part doesnt need any more cuts. The second part needs to be cut at point 3 metres (5 - 2) from its begining. The cost for making this cut will be stored in the hash table as

Value(4#3) = 4

So value of (6#2#5) = 6 + 4 = 10.

Now the total cost = 10 + 4 + 10 = 24

In the example chosen above, we didnt have any cut patterns that repeated. So that the costs stored for the cut patterns in the memory were never used.

Now consider this example, wood of length = 10 metres, points a1 = 1 metre, a2 = 3 metres, a3 = 5 metres, a4=6 metres, a5=8 metres

In this example, once we cut the wood at a3=5 metres, we have two woods of the same cut pattern. The pattern is (5#1#3). So it is enough if we calculated the cost for one part. For the other part we can straight away take the cost from the memory.

Now to the recurrence relation,

C(L, a1, a2, ... an) = C(L) + C(L1, a1, a2, ... aL1) + C({L-L1}, {aL1+1 - aL1}, {aL1+2 - aL1}, ... {an - aL1})

where C = Cost

• L = Length of the initial piece of wood. C(L) = L
• a1... an = Points at which the wood has to be cut
• L1 = Point nearest to L/2 where the first cut is made.
• aL1 = Point of cut at length L1
• aL1+1 = The next point after aL1 that is marked for a cut.

I will try to write a C program for the above problem and post it later. Open for comments on the way the solution is explained and if there are other better solutions for this.