切割棒，使得最小化成本

本文介绍了切割棒，使得最小化成本的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

您必须切断与长度→一棒成数块。已经削减将在地方取得了 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.

我是pretty的肯定，这是一个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）返回切割长度的棒的最低成本 stick_length 在 C_1，C_2，...，C_N ，复发的关系会是这个样子

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的解决方案：

One more DP solution:

让我们COST（A，B）是切割个和b个切点之间的线段的最佳性价比。很显然，COST（一，一）和COST（A，A + 1）是零。我们可以计算成本的最佳值（A，B）通过所有的中间点最小割的+ 1 ... B-1以及自己的段长度。因此，我们可以填补三角形桌子角对角，找到最后的结果成本（开始，结束）与O（N ^ 3）的时间复杂度和O（N ^ 2）空间

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

德尔福code（输出成本20序列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]]);