切割木板的最低成本

Question

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

我们可以沿着水平和垂直线切割电路板，每个切割将电路板分成较小的部分。根据切割是沿着水平线还是垂直线进行，每块切割板都有成本。让我们用x [1]，x [2]，...，x [n-1]和水平线以y [1]，y [2]表示沿连续垂直线切割的成本。 ...，y [m-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开始切割。第一次剪切将是水平的，其中cost = 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行的切割开始的每个切割，等等。但显然它效率太低了。那么如何解决这个问题呢？

Answer 1

那么，这似乎很简单。因此，你需要做所有的削减和最大限度地减少昂贵的削减数量，你应该按他们的成本来订购。

虽然有一个问题 - 如果您的裁剪价格相同，那么您需要对它们进行分组。假设你必须做5个切割，每个切割6个，4个在列上，2个在行上，并且板子是未切割的。如果您先裁减2行，则您的费用为2 * 6 + 4 * 3 * 6 = 14 * 6。如果你以其他方式做，你会得到4 * 6 + 2 * 4 * 6 = 12 * 6。

规则是做高价削减第一和第一沿轴，其中大多数。

编辑：为了跟踪你有多少段，你需要跟踪你对其他轴的切割。 o如果您在行上制作了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.flatten 

Answer 2

分割线的选择应该是在降低成本的顺序，实现最低的总成本。

证明：

任何削减的 “错误” 有序序列必须有2点连续的削减C1和C2与成本C1和C2，使得C1 < C2和C1 C2来之前。如果两次切割彼此平行，则切换其顺序不会影响总成本。

另一方面，如果C1是垂直的，而C2是水平的（不失一般性），那么我们可以按如下方式检查它。假设V0是在应用C1之前的垂直片段的数量，并且H0是C1之前的水平片段的数量。

• 施加C1和成本然后C2是：H0 * C1 +（V0 + 1）* C2
• 施加C2的成本，然后C1为：V0 * C2 +（H0 + 1）* c1

第一个表达式减去第二个表达式c2-c1，它是正数。换句话说，交换C1和C2可降低成本。结论：使用一系列交换，任何无序序列都可以转化为有序序列，这样总成本只能被降低。这完成了最优性证明。

注意：如果以相同成本进行多次裁减，其内部排序完全不会影响总成本，如上面的计算所示。在降低成本

Answer 3

只要选择切割线，这里是C++代码

代码：

#include <bits/stdc++.h> 
using namespace std; 

int main() { 
long int t; 
cin >> t; 
while(t--){ 
    long long int m,n,*x,*y,i,j,sum,cx,cy,modu = 1000000007; 
    cin >> m >> n; 
    x = new long long int[m-1]; 
    y = new long long int[n-1]; 
    for(i=0;i<m-1;i++) 
    cin >> x[i]; 
    for(i=0;i<n-1;i++) 
    cin >> y[i]; 
    sort(y,y+n-1); 
    sort(x,x+m-1); 

    i=m-1-1;sum=0;j=n-1-1;cx = 1;cy =1; 
    while(i>=0 && j >=0){ 

     if(x[i] > y[j]){ 
      sum += (x[i]*cy)%modu; 
      cx++; 
      i--; 
     } 
     else{ 
      sum += (y[j]*cx)%modu; 
      cy++; 
      j--; 
     } 
    } 

    while(i>=0){ 
     sum += (x[i]*cy)%modu; 
     i--; 
    } 
    while(j>=0){ 
     sum += (y[j]*cx)%modu; 
     j--; 
    } 

    cout << sum%modu << endl; 
} 
return 0; 
} 

Answer 4

这个问题可以通过贪心算法的方法来解决。

只有1条规则： - 按降序选择削减成本，如果两个或更多成本相等，则选择任意一个。 这里是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 cost 

Answer 5

这里是用Python 2

1. 我贪心算法的方法来降低成本，最便宜的位置，必须先切断
2. 的次数减少是（M - 1）+（N - 1）
3. 内部顺序并不重要。因为最终所有的位置将被削减
4. 跟踪每个维度削减当前数量（NX，NY）

代码

M,N = [int(x) for x in raw_input().split()] 
CY = sorted([int(x) for x in raw_input().split()], reverse=True) 
CX = sorted([int(x) for x in raw_input().split()], reverse=True) 
nx = 1 
ny = 1 
minC = 0 
i = 0 
j = 0 
total = M - 1 + N - 1 
for _ in range(0,total): 
    #j == N - 1 to check if CX is exhausted 
    if (j == N - 1 or (i != M -1 and CY[i] > CX[j])): 
     minC += CY[i]*nx 
     ny += 1 
     i += 1 
    else: 
     minC += CX[j]*ny 
     nx += 1 
     j += 1 

print minC%(1000000000+7) 

Answer 6

虽然问题已经回答，我写这个提供了一个非正式的，可能是直观的解释：

我们必须做（n-1）*（m-1）削减，所以我们只需要决定首先选择哪个切割。

让我们说，我们可以选择两个削减C1和C2，成本C1和C2。让我们说c1> c2。假设整个事件的总当前成本用C表示C

如果我们选择了比这个步骤晚的C1，它至少会添加（取决于是否将它添加到下一步中）c1到整体成本，C。 如果我们选择C2比这一步晚，它将增加至少c2的整体成本，C。

所以我们可以说我们现在可以贪婪地选择C1，因为以后选择它会更糟稍后再选择C2。

因此，我们选择降低成本的顺序，而不考虑切割类型（水平，垂直）。