algorithm - Optimally cutting a stick at specified locations

Question

You have to cut a stick with length l into several pieces. Cuts have to be made at locations c1, c2, c3, ..., cn, where ci is an integer between 1 and n-1 (inclusive). The cost of a cut is equal to the length of the stick on which it is made. What should be the order of the cuts to minimize the overall cost of the operation?

For example, consider a stick of length 10 and cuts have to be made at locations 2, 4, 7. You could cut the sticks in the order given. The first cut would cost 10, since the stick is of length 10. The second cut would cost 8, since the remaining stick on which the cut is made is of length 10 - 2 = 8. The last cut would cost 6, since the length of the remaining stick is 10 - 4 = 6. The total cost is 10 + 8 + 6 = 24

But if we cut the stick in the order: 4, 2, 7, we get the cost of 10 + 4 + 6 = 20 which is better for us.

Design an algorithm to solve the problem.

I'm pretty sure this is a DP problem. A tantalizing recurrence relation I could see was the fact that if we cut a stick, we get two smaller sticks. If we know the optimum solution for these two sticks, we can easily figure out the optimum solution for the larger stick. But this would be very inefficient.

If you have a recursive function min_cost(stick_length, c_1, c_2, ..., c_n) which returns the minimum cost of cutting a stick of length stick_length at c_1, c_2, ..., c_n, the recurrence relation would look something like this

min_cost(stick_length, c_1, c_2, ..., c_n) =
    stick_length 
    + minimum(min_cost(c_1, a_1, a_2, ..., a_i) 
    + min_cost (stick_length - c_1, 
                a_(i+1), ..., a_(n-1)),
                min_cost(c_2, a_1, a_2, ..., a_i) 
    + min_cost(stick_length - c_2, 
               a_(i+1), ..., a_(n-1)), ... , 
               min_cost(c_n, a_1, a_2, ..., a_i)
    + min_cost(stick_length - c_n,
                a_(i+1), ..., a_(n-1)))`,

where a_1, a_2, ..., a_n is a permutation of the remaining places to be cut. We will have to pass all possible permutations to the recurrence function not just one as I have written.

This is obviously impractical. How do I solve this?

Answer 1

One more DP solution:

Let's COST(a,b) is the best cost of cutting the segment between a-th and b-th cut point. It is clear that COST(a,a) and COST(a,a+1) is zero. We can compute the best value of COST(a,b) as minimum of cuts through all the middle points a+1...b-1 plus own segment length. So we can fill triangle table diagonal by diagonal and find final result as COST(start,end) with O(N^3) time complexity and O(N^2) space

Delphi code (outputs Cost 20 Sequence 4 2 7)

var
  Cuts: TArray<Integer>;
  Cost: array of array of Integer;
  CutSequence: array of array of String;
  N, row, col, leftpos, rightpos, cutpos, Sum: Integer;
begin
  Cuts := TArray<Integer>.Create(0, 2, 4, 7, 10); // start, cuts, end points
  N := Length(Cuts);
  SetLength(Cost, N, N);  //zero-initialized 2D array
  SetLength(CutSequence, N, N);  //zero-initialized 2D array

  for rightpos := 2 to N - 1 do
    for leftpos := rightpos - 2 downto 0 do begin //walk along the diagonals
                                                  //using previously computed results
      //find the best (mincost) cut
      Cost[leftpos, rightpos] := MaxInt; //big value
      for cutpos := leftpos + 1 to rightpos - 1 do begin
        Sum := Cost[leftpos, cutpos] + Cost[cutpos, rightpos];
        if Sum < Cost[leftpos, rightpos] then begin
          Cost[leftpos, rightpos] := Sum;
          //write down best sequence
          CutSequence[leftpos, rightpos] := Format('%d %s %s', [Cuts[CutPos],
            CutSequence[leftpos, cutpos], CutSequence[cutpos, rightpos]]);
        end;
      end;

      //add own length
      Cost[leftpos, rightpos] :=
        Cost[leftpos, rightpos] + Cuts[rightpos] - Cuts[leftpos];
    end;

  //show the best result
  Caption := Format('Cost %d  Sequence %s',[Cost[0, N-1], CutSequence[0, N-1]]);