切割木板的最低成本

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。

因此，我們選擇降低成本的順序，而不考慮切割類型（水平，垂直）。