切木板的最低成本
给定一个由M木块组成的木板，我们需要找到将木板分解成方形木片的最小成本。
我们可以沿水平和垂直线切割板，每一次切割都将板分成较小的部分。板的每一个切割都有一个成本，这取决于裁剪是沿着一条水平的还是垂直的。
让我们用x1，x2，…表示沿着连续的垂直线切割它的成本。，xn-1，并沿水平线使用y1，y2，…，ym-1。如果削减(成本c)并通过n个分段，那么这个削减的总成本将为n*c。
将整个板切成一个正方形的成本是用来将整个板切成大小为1x1的方形木片的连续裁剪成本之和。
将整个木板折成大小为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*4 + 1*3 + 1*6 = 42。
我的方法是:从第1行到第2行之间开始检查每一次裁剪，所以on.But显然太inefficient.So了，如何解决这个问题？
回答 6
Stack Overflow用户
发布于 2014-02-23 17:35:09
看来这很简单。因此，您需要做所有的削减，并尽量减少最昂贵的削减，您应该只是按他们的成本订购。
有一个陷阱-如果你有相同的价格削减，那么你需要分组他们。假设你必须做5次降价，每个6次，4次在列上，2次在行和板是未剪裁。如果您先削减2行，您的成本是2 * 6 + 4 * 3 * 6 = 14 * 6。如果你用相反的方法来做，你就会得到4 * 6 + 2 * 4 * 6 = 12 * 6。
规则是先做高价格的削减，然后沿着轴进行第一次削减，这是其中的大部分。
编辑：，以跟踪您有多少段，您需要跟踪您所做的切割到其他轴。如果您对行进行了3裁剪，那么裁剪列将需要3 + 1裁剪。如果您已经剪切了5列和3行，那么裁剪另一行将始终需要遍历每一列裁剪行，这意味着您必须剪切5 + 1次数。
编辑2: --因为我的示例不对，这是如何使用问题中的情况：
cut_x = [2, 1, 3, 1, 4]
cut_y = [4, 1, 2]
list_of_cuts_grouped_by_cost_descending = [[x5, y1], [x3], [x1, y3], [x2, y2, x4]]
cut_groups_ordered_by_most_cut_axis = [[x5, y1], [x3], [x1, y3], [x2, x4, y2]]
return cut_groups_ordered_by_most_cut_axis.flattenStack Overflow用户
发布于 2014-02-23 21:31:54
分割线的选择应以降低成本的顺序进行，以达到最小的总成本。
证明：
任何“错误”顺序的削减序列都必须有两个连续的削减-- 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可以降低成本。
结论:利用一系列交换序列，可以将任意非有序序列转化为有序序列，从而降低总成本。这就完成了最优性证明。
注:在多次削减相同成本的情况下，它们的内部订单根本不影响总成本，如上面的计算所示。
Stack Overflow用户
发布于 2016-01-01 03:32:31
这个问题可以用贪婪算法来解决。
只有一条规则:-按递减顺序选择削减成本，如果两个或多个成本相等，选择任意一个。这里是python的解决方案：-
M, N = map(int, raw_input().strip().split(' '))
Y = map(int, raw_input().strip().split(' '))
X = map(int, raw_input().strip().split(' '))
Y.sort(reverse=True)
X.sort(reverse=True)
y_cut = x_cut = 1 #To count the number of segments
cost = i = j = 0
while i < X.__len__() and j < Y.__len__():
if X[i] >= Y[j]:
x_cut = x_cut + 1
cost = cost + (X[i]*y_cut)
i = i+1
else:
y_cut = y_cut + 1
cost = cost + (Y[j]*x_cut)
j = j+1
while i < X.__len__():
cost = cost + (X[i]*y_cut)
i = i+1
while j < Y.__len__():
cost = cost + (Y[j]*x_cut)
j = j+1
print costhttps://stackoverflow.com/questions/21971657
复制相似问题
腾讯云开发者
