algorithm - 切割木板的最低成本

Question

给定一 block 由 M X N 个方形木 block 组成的木板，我们需要找到将木板分成方形木 block 的最小成本。

我们可以沿水平线和垂直线切割木板，每次切割都会将木板分成更小的部分。板的每次切割都有成本，具体取决于切割是沿水平线还是垂直线进行。

让我们用 x[1]、x[2]、…、x[n-1] 和水平线 y[1]、y[2]、… , y[m-1].如果进行了一次切割(成本为 c)并且它通过了 n 个段，那么这次切割的总成本将为 n*c。

将整 block 板切割成单个正方形的成本是将整 block 板切割成尺寸为 1x1 的正方形木 block 所用的连续切割成本的总和。

将整 block 木板分成 1x1 大小的正方形的最小成本是多少。

示例:让我们采用 6*4 网格。

让沿行切割成本如下:[2 1 3 1 4]

按以下方式削减列成本:[4 1 2]

这里的答案是42

我们应该按顺序使用 y5、x1、y3、y1、x3、y2、y4 和 x2 开始切割。第一次切割将是水平切割，其中成本 = y5 = 4。接下来我们将使用 x1 进行垂直切割。由于此切割穿过两个线段(由之前的垂直切割创建)，因此总成本将为 2*x1 = 2*4。类似地，下一个水平切割 (y3) 将穿过两个线段，成本为 2*y3 = 2*3。我们可以以类似的方式进行，得到总成本为 4 + 4*2 + 3*2 + 2*2 + 2*4 + 1*3 + 1*3 + 1*6 = 42。

我的方法:从第 1 行到第 2 行之间的 cut 开始检查每个 cut，然后依此类推。但显然效率太低了。那么如何解决这个问题？

Answer 1

拆分线的选择应按成本降序排列，以实现总成本最小。

证明:

任何“错误”排序的切割序列必须有 2 个连续的切割 C1 和 C2，成本为 c1 和 c2，这样 c1

如果另一方面 C1 是垂直的而 C2 是水平的(不失一般性)，那么我们可以按如下方式检查它。令V0为应用C1之前的垂直片段数，H0为应用C1之前的水平片段数。

• 先应用​​C1再应用C2的代价是:H0*c1 + (V0+1)*c2
• 先应用​​C2再应用C1的代价是:V0*c2 + (H0+1)*c1

第一个表达式减去第二个表达式得到正数 c2-c1。换句话说，交换 C1 和 C2 可以降低成本。

结论:使用一系列交换，任何无序序列都可以转换为有序序列，这样总成本只能降低。这样就完成了最优性证明。

注意:如果成本相同的多次切割，它们的内部排序根本不会影响总成本，如上面的计算所示。