在指定位置最佳切割木棍

小编典典

在指定位置最佳切割木棍

algorithm

您必须将一根长短的棍子切成l几块。必须在位置进行切割c1, c2, c3, ..., cn，其中ci是1和之间的整数n-1（含）。切割的成本等于进行切割的木棍的长度。为了最大程度地降低运营成本，削减的顺序应该是什么？

例如，考虑一根长条10，必须在位置上进行切割2, 4, 7。您可以按照给定的顺序切割木棍。第一次切割会花费很多10，因为木棍的长度是一定的10。第二个切口会花费成本8，因为进行切口的剩余棍棒的长度很大10 - 2 = 8。最后一次切割会花费成本6，因为剩下的棍子的长度是10 - 4 = 6。总费用是10 + 8 + 6 = 24

但是，如果我们按以下顺序切割棒：4, 2, 7，我们得到的成本10 + 4 + 6 = 20对我们来说更好。

设计一种解决该问题的算法。

我很确定这是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剩余的待切割位置的排列在哪里。我们将不得不将所有可能的排列传递给递归函数，而不仅仅是我所写的。

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

阅读 282

2020-07-28

共1个答案

小编典典

另一种DP解决方案：

让我们的COST（a，b）是切割第a个和第b个切割点之间的线段的最佳成本。显然，COST（a，a）和COST（a，a +
1）为零。我们可以计算出COST（a，b）的最佳值，因为它是对所有中间点a + 1 …
b-1加上自己的线段长度的最小切割。因此我们可以用对角线填充对角线三角形表，并以O（N ^ 3）时间复杂度和O（N ^
2）空间找到最终结果作为COST（start，end）

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

2020-07-28