在指定位置最佳切割木棍 [英] Optimally cutting a stick at specified locations

问题描述

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

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?

例如，考虑一根长度为 10 的棒，并且必须在 2、4、7 。您可以按照给定的顺序切割木棍。第一次切割的成本为 10 ，因为棒的长度为 10 。第二次切割的成本为 8 ，因为进行切割的其余棒的长度为 10-2 = 8 。最后一次切割的成本为 6 ，因为剩余棒的长度为 10-4 = 6 。总成本为 10 + 8 + 6 = 24

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

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

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问题。我能看到的一个诱人的复发关系是，如果我们切一根棍子，就会得到两根较小的棍子。如果我们知道这两个棒的最佳解决方案，我们可以轻松地找出较大棒的最佳解决方案。但这将是非常低效的。

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.

如果您有一个递归函数 min_cost（stick_length，c_1，c_2，...，c_n）在 c_1，c_2，...，c_n ，重复关系上切割长度为 stick_length 的棍子的最小成本看起来像这样

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

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

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?

推荐答案

另一个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）的最终结果

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代码（输出 Cost 20 Sequence 4 2 7 ）

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

这篇关于在指定位置最佳切割木棍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！