Optimally cutting a stick at specified locations

algorithm

Solution

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]]);

Problem

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?

Original source