Geek Answers Handbook

The minimum cost of cutting a wooden board

Given a wooden board consisting of MXN wooden square pieces, we need to find the minimum cost of breaking the board into square wooden pieces.

We can cut the board in horizontal and vertical lines, and each cut divides the board into smaller parts. Each section of the board has a cost depending on whether the section is made along a horizontal or vertical line.

Denote the cost of cutting along successive vertical lines with x [1], x [2], ..., x [n-1] and along horizontal lines with y [1], y [2], ..., y [m-1]. If the cut (cost c) is made and passes through n segments, then the total cost of this cut will be n * c.

The cost of cutting the entire board into individual squares is the sum of the cost of successive cuts used to cut the entire board into 1x1 square wooden pieces.

What is the minimum cost of breaking an entire wooden board into 1x1 squares.

Example: take a 6 * 4 grid.

Let me cut the line costs as follows: [2 1 3 1 4]

The column cost reduction as follows: [4 1 2]

Here the answer will be 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- , . , , . ?

+4
6

, , . , , .

- , . , 5 6 , 4 , 2 . 2 , 2 * 6 + 4 * 3 * 6 = 14 * 6. -, 4 * 6 + 2 * 4 * 6 = 12 * 6.

- , .

: , , , . o 3 , 3 + 1. 5 colours 3 rows, , , 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
-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 .

. , , . .

. , .

+15

Greedy Algorithm.

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
+2

, , , :

(n-1) * (m-1) , , .

, C1 C2 c1 c2. , c1 > c2. C

C1 , ( , ) c1 , C. C2 , c2 , C.

, , C1 , , C2 .

, (, ) .

+1

, ++

:

#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;
}
0

Here is my Greedy Algorithm approach in Python 2.

  • To minimize costs, you must first reduce the most expensive locations.
  • The number of abbreviations (M - 1) + (N - 1)
  • The internal order does not matter. Because ultimately all locations will be reduced.
  • Keep track of the current number of cuts in each dimension (nx, ny)

the code

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)
0
source

More articles:


All Articles