algorithm - 在指定位置最佳切割木棒

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.

我很确定这是一个 DP 问题。我可以看到一个诱人的递归关系是这样一个事实，即如果我们切一根木棍，我们会得到两根更小的木棍。如果我们知道这两根棍子的最优解，我们就可以很容易地找出更大棍子的最优解。但这将是非常低效的。

如果你有一个递归函数 min_cost(stick_length, c_1, c_2, ..., c_n) 它返回切割长度为 stick_length 的棍子的最小成本c_1, c_2, ..., c_n，递归关系看起来像这样

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)))`,

其中 a_1, a_2, ..., a_n 是剩余待切割位置的排列。我们必须将所有可能的排列传递给递归函数，而不仅仅是像我写的那样。

这显然是不切实际的。我该如何解决这个问题？

Answer 1

另一种DP方案:

假设 COST(a,b) 是在第 a 和第 b 个切割点之间切割线段的最佳成本。很明显，COST(a,a) 和 COST(a,a+1) 为零。我们可以将 COST(a,b) 的最佳值计算为通过所有中间点 a+1...b-1 的最小切割加上自己的线段长度。所以我们可以用对角线对角线填充三角形表，并找到最终结果为 COST(start,end)，时间复杂度为 O(N^3)，空间为 O(N^2)

Delphi 代码(输出 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]]);