Cutting algorithm of two dimensional board

Question

I have problem with my homework.

Given a board of dimensions m x n is given, cut this board into rectangular pieces with the best total price. A matrix gives the price for each possible board size up through the original, uncut board.

Consider a 2 x 2 board with the price matrix:

3 4

3 6

We have a constant cost for each cutting for example 1.
Piece of length 1 x 1 is worth 3.
Horizontal piece of length 1 x 2 is worth 4.
Vertical piece of length 1 x 2 is worth 3.
Whole board is worth 6.

For this example, the optimal profit is 9, because we cut board into 1 x 1 pieces. Each piece is worth 3 and we done a 3 cut, so 4 x 3 - 3 x 1 = 9.

Second example:

1 2

3 4

Now I have to consider all the solutions:

• 4 1x1 pieces is worth 4x1 - (cost of cutting) 3x1 = 1
• 2 horizontal 1x2 is worth 2x2 - (cost of cutting) 1x1 = 3
• 2 vertical 1x2 is worth 3x2 - (cost of cutting) 1x1 = 5 -> best optimal profit
• 1 horizontal 1x2 + 2 x (1x1) pieces is worth 2 + 2 - (cost of cutting) 2 = 2
• 1 vertical 1x2 + 2 x (1x1) pieces is worth 3 + 2 - (cost of cutting) 2 = 3

I've read a lot about rod cutting algorithm but I don't have any idea how to bite this problem. Do you have any ideas?

Answer 1

I did this in Python. The algorithm is

• best_val = value of current board
• check each horizontal and vertical cut for better value
  • for cut point <= half the current dimension (if none, return initial value)
  • recur on the two boards formed
  • if sum of values > best_val
  • ... best_val = that sum
  • ... record cut point and direction
• return result: best_val, cut point, and direction

I'm not sure what you'll want for return values; I gave back the best value and tree of boards. For your second example, this is

(5, [[2, 1], [2, 1]])

Code, with debugging traces (indent and the labeled prints):

indent = ""
indent_len = 3

value = [[1, 2],
         [3, 4]]

def best_cut(high, wide):
    global indent
    print indent, "ENTER", high, wide
    indent += " " * indent_len

    best_val = value[high-1][wide-1]
    print indent, "Default", best_val
    cut_vert = None
    cut_val = best_val
    cut_list = []

    # Check horizontal cuts
    for h_cut in range(1, 1 + high // 2):
        print indent, "H_CUT", h_cut
        cut_val1, cut_list1 = best_cut(h_cut, wide)
        cut_val2, cut_list2 = best_cut(high - h_cut, wide)
            cut_val = cut_val1 + cut_val2

        if cut_val > best_val:
            cut_list = [cut_list1, cut_list2]
            print indent, "NEW H", h_cut, cut_val, cut_list
            best_val = cut_val
            cut_vert = False
            best_h = h_cut

    # Check vertical cuts
    for v_cut in range(1, 1 + wide // 2):
        print indent, "V_CUT", v_cut
        cut_val1, cut_list1 = best_cut(high, v_cut)
        cut_val2, cut_list2 = best_cut(high, wide - v_cut)
        cut_val = cut_val1 + cut_val2

        if cut_val > best_val:
            cut_list = [cut_list1, cut_list2]
            print indent, "NEW V", v_cut, cut_val, cut_list
            best_val = cut_val
            cut_vert = True
            best_v = v_cut

    # Return result of best cut
    # Remember to subtract the cut cost
    if cut_vert is None:
        result = best_val  , [high, wide]
    elif cut_vert:
        result = best_val-1, cut_list
    else:
        result = best_val-1, cut_list

    indent = indent[indent_len:]
    print indent, "LEAVE", cut_vert, result
    return result

print best_cut(2, 2)

Output (profit and cut sizes) for each of the two tests:

(9, [[[1, 1], [1, 1]], [[1, 1], [1, 1]]])

(5, [[2, 1], [2, 1]])

Answer 2

Let f(h,w) represent the best total price achievable for a board with height h and width w with cutting price c. Then

f(h,w) = max(
  price_matrix(h, w),
  f(i, w) + f(h - i, w) - c,
  f(h, j) + f(h, w - j) - c
)
for i = 1 to floor(h / 2)
for j = 1 to floor(w / 2)

Here's a bottom-up example in JavaScript that returns the filled table given the price matrix. The answer would be in the bottom right corner.

function f(prices, cost){
  var m = new Array(prices.length);

  for (let i=0; i<prices.length; i++)
    m[i] = [];

  for (let h=0; h<prices.length; h++){
    for (let w=0; w<prices[0].length; w++){

      m[h][w] = prices[h][w];

      if (h == 0 && w == 0)
        continue;

      for (let i=1; i<(h+1>>1)+1; i++)
        m[h][w] = Math.max(
          m[h][w],
          m[i-1][w] + m[h-i][w] - cost
        );

      for (let i=1; i<(w+1>>1)+1; i++)
        m[h][w] = Math.max(
          m[h][w],
          m[h][i-1] + m[h][w-i] - cost
        );
    }
  }

  return m;
}

$('#submit').click(function(){
  let prices = JSON.parse($('#input').val());
  let result = f(prices, 1);
  let str = result.map(line => JSON.stringify(line)).join('<br>');
  $('#output').html(str);
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<textarea id="input">[[3, 4],
[3, 6]]</textarea>
<p><button type="button" id="submit">Submit</button></p>
<div id="output"><div>