Help with a dynamic programming solution to a pipe cutting problem

Question

I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem

You have to cut a metal pipe into several pieces. To do so, you bring it to a company that charges money according to the length of the pipe being cut. Their cutting method means that only one cut can be made at a time.

Different ways in cutting the pipe can lead to different overall total prices. For example, suppose that a pipe of length 10 meters has to be cut at 2, 4, and 7 meters from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first pipe was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.

Figure out (a method to determine) what is the cheapest price that is possible (to make sure that the company isn't cheating you). The procedure that you write (in Java) should return a single integer, which will be the cheapest possible total cost for performing all of the cuts. Only one cut can be performed at a time, and the cost of making a cut is equal to the length of the pipe being cut (before the cut is performed).

But I'm having trouble knowing where I even need to start. If anyone could point me in the direction of where I can research similar problems or give me an idea of what I should be thinking about with this problem it would be great.

Answer 1

For me, it makes more sense to think about this problem in reverse. The problem is posed as a destructive process - you have 1 pipe, and you split it into many. However, in terms of the cost calculation, the reverse process results in the same answer. That is, if you take the resulting pipe segments and start gluing them back together, using the sum of the length of the two pieces you're gluing as the cost of the operation, you end up with the same cost.

So then the question becomes the following:

given a set of pipe segments, what is the cheapest order of gluing segments together until you have only one segment? This assumes a cost function where c(x1,x2) = len(x1) + len(x2).

This is trivial when you have two segments. There's only one way to glue them together, so that has to be the cheapest way.

With three segments, it starts to be a bit more interesting.

Lets say we have lengths x1, x2, and x3. We have three options for our first operation: x1 + x2, x2 + x3, and x1 + x3. No matter what values are in x1, x2, and x3, the operation after this one will cost the same. That is to say the following:

(x1 + x2) + x3 == (x2 + x3) + x1 == (x1 + x3) + x2

As a result, the cheapest way of putting the three pieces of pipe back together is going to be the way that has the cheapest first step.

Then the question becomes, which of the first steps is the cheapest?

That depends on what the values in x1, x2, and x3 are. Lets assume the three values are in ascending order. So x1 <= x2 <= x3. Now you can determine which starting pair is the cheapest, right? Its the pair containing the smallest values, or x1 and x2. Note that there is the possibility that two or more of the three values are the same. I'll leave it up to you to convince yourself that such a scenario is not a problem.

So we've got a solution for either 2 or 3 pieces. This should give you some insight towards a general solution.