Minimum cost to cut wooden board

Question

Given a wooden board composed of M X N wooden square pieces we need to find the minimal cost of breaking the board into square wooden pieces.

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

Let us denote the costs of cutting it along consecutive vertical lines with x[1], x[2], …, x[n-1] and along horizontal lines with y[1], y[2], …, y[m-1]. If a cut (of cost c) is made and it passes through n segments, then total cost of this cut will of n*c.

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

Whats the minimal cost of breaking the whole wooden board into squares of size 1x1.

Example : Let us take 6*4 grid.

Let cutting along rows cost is as follow : [2 1 3 1 4]

Cutting along column cost as follow : [4 1 2]

Here answer will be 42

We should start cutting using y5, x1, y3, y1, x3, y2, y4 and x2, in order. First cut will be a horizontal one where cost = y5 = 4. Next we will do a vertical cut with x1. Since this cut passes through two segments (created by previous vertical cut), it’s total cost will be 2*x1 = 2*4. Similarly next horizontal cut (y3) will pass through two segments and will cost 2*y3 = 2*3. We can proceed in similar way and get overall cost as 4 + 4*2 + 3*2 + 2*2 + 2*4 + 1*3 + 1*3 + 1*6 = 42.

My Approach : Check for each cut starting from cut between 1 and 2 nd row then so on.But obviously its too inefficient.So how to solve this problem?

Answer 1

The selection of the split lines should be in decreasing cost order for achieving minimal total cost.

Proof:

Any "incorrectly" ordered sequence of cuts must have 2 consecutive cuts C1 and C2 with costs c1 and c2, such that c1<c2 and C1 comes before C2. If the two cuts are parallel to each other, then switching their order has no effect on the total cost.

If on the other hand C1 is vertical while C2 is horizontal (without loss of generality), then we can examine it as follows. Let V0 be the number of vertical fragments before C1 is applied, and H0 be the number of horizontal fragments prior to C1.

• The cost of applying C1 and then C2 is: H0*c1 + (V0+1)*c2
• The cost of applying C2 and then C1 is: V0*c2 + (H0+1)*c1

The first expression minus the second gives c2-c1, which is positive. In other words, swapping C1 and C2 reduces the cost.

Conclusion: Using a series of swaps, any non-ordered sequence can be transformed into an ordered one, such that the total cost can only be reduced. This completes the optimality proof.

Note: In case of multiple cuts with the same cost, their internal ordering doesn't affect the total cost at all, as seen in the calculation above.