二维板材的切割算法

Question

二维板材的切割算法

5

我有一个作业问题。

给定一个尺寸为 m x n 的矩阵，将该矩阵切成最优总价值的矩形块。一个矩阵给出了每个可能的矩形大小直到原始未切割的矩阵的价格。

考虑一个价格矩阵为：

3 4

3 6

我们每次切割的成本是固定的，例如 1。
长度为 1 x 1 的零件价值为 3。
长度为 1 x 2 的水平零件价值为 4。
长度为 1 x 2 的垂直零件价值为 3。
整个板的价值为 6。

对于这个例子，最优的利润是 9，因为我们将板子切成了 1 x 1 的小块。每个小块价值为 3，我们进行了 3 次切割，所以总价值为 4 x 3 - 3 x 1 = 9。

第二个例子：

1 2

3 4

现在我必须考虑所有的解决方案：

4个1x1的块材料价值为4x1 - (切割成本) 3x1 = 1
2个水平1x2的块材料价值为2x2 - (切割成本) 1x1 = 3
2个垂直1x2的块材料价值为3x2 - (切割成本) 1x1 = 5 -> 最佳的最优利润
1个水平1x2和2个1x1的块材料价值为2 + 2 - (切割成本) 2 = 2
1个垂直1x2和2个1x1的块材料价值为3 + 2 - (切割成本) 2 = 3

我读了很多有关于棒材切割算法的文章，但我不知道如何解决这个问题。你有什么想法吗？

- Tetsu

尝试在其他 STACK EXCHANGE 社区 中提问，例如“学术界”。 - Green

我已经在主贴中添加了第二个示例。 - Tetsu

4个回答

1

让f(h,w)表示高度为h，宽度为w的板材在切割价格c下可达到的最佳总价格。则有：

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)

这是一个JavaScript的自下而上的示例，根据价格矩阵返回填充的表格。答案将在右下角。

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>

- גלעד ברקן

告诉我，你为什么在for循环中使用位运算符？ - Tetsu

@Tetsu x >> 1 相当于 floor(x / 2)。 - גלעד ברקן

那你为什么会在半场时切得高而宽呢？ - Tetsu

@Tetsu 如果我们在 3 处将 w = 10 切割，我们会得到 (3，7)。如果我们在 7 处将 w = 10 切割，我们会得到 (7，3)。它们是一样的，我们想要避免重复计算。 - גלעד ברקן

0

根据您的答案，我已经准备好了自底向上和自顶向下的实现。

自底向上：

function bottomUp($high, $wide, $matrix){
    $m = [];

    for($h = 0; $h < $high; $h++){
        for($w = 0; $w < $wide; $w++){
           $m[$h][$w] = $matrix[$h][$w];

            if($h == 0 && $w == 0){
                continue;
            }

            for($i = 1; $i < ($h + 1 >> 1) + 1; $i++){
                $m[$h][$w] = max(
                    $m[$h][$w],
                    $m[$i - 1][$w] + $m[$h - $i][$w] - CUT_COST
                );
            }

            for($i = 1; $i < ($w + 1 >> 1) + 1; $i++){
                $m[$h][$w] = max(
                    $m[$h][$w],
                    $m[$h][$i - 1] + $m[$h][$w - $i] - CUT_COST
                );
            }            
        }        
    }

    return $m[$high-1][$wide-1];
}

自顶向下：

function getBestCut($high, $wide, $matrix){
    global $checked;

    if(isset($checked[$high][$wide])){
        return $checked[$high][$wide];
    }

    $bestVal = $matrix[$high-1][$wide-1];
    $cutVert = CUT_VERT_NONE;
    $cutVal = $bestVal;
    $cutList = [];

    for($hCut = 1; $hCut < 1 + floor($high/2); $hCut++){
        $result1 = getBestCut($hCut, $wide, $matrix);
        $cutVal1 = $result1[0];
        $cutList1 = $result1[1];
        $result2 = getBestCut($high - $hCut, $wide, $matrix);
        $cutVal2 = $result2[0];
        $cutList2 = $result2[1];        
        $cutVal = $cutVal1 + $cutVal2;

        if($cutVal > $bestVal){
            $cutList = [$cutList1, $cutList2];
            $bestVal = $cutVal;
            $cutVert = CUT_VERT_FALSE;
            $bestH = $hCut;
        }

        $checked[$hCut][$wide] = $result1;
        $checked[$high - $hCut][$wide] = $result2;
    }

    for($vCut = 1; $vCut < 1 + floor($wide/2); $vCut++){
        $result1 = getBestCut($hCut, $vCut, $matrix);
        $cutVal1 = $result1[0];
        $cutList1 = $result1[1];
        $result2 = getBestCut($high, $wide - $vCut, $matrix);
        $cutVal2 = $result2[0];
        $cutList2 = $result2[1];        
        $cutVal = $cutVal1 + $cutVal2;   

        if($cutVal > $bestVal){
            $cutList = [$cutList1, $cutList2];
            $bestVal = $cutVal;
            $cutVert = CUT_VERT_TRUE;
            $bestH = $vCut;
        }      

        $checked[$hCut][$vCut] = $result1;
        $checked[$high][$wide - $vCut] = $result2;        
    }

    if($cutVert == CUT_VERT_NONE){
        $result = [$bestVal, [$high, $wide]];
    }else if($cutVert == CUT_VERT_TRUE){
        $result = [$bestVal - CUT_COST, $cutList];
    }else{
        $result = [$bestVal - CUT_COST, $cutList];
    }

    return $result;
}

请问这个方法的实现是否正确？

我想知道自顶向下的方法的时间复杂度是否为 O(m^2*n^2)？

- Tetsu

0

关于问题的一些想法而非答案：

我学习动态规划已经很久了，但我写了以下伪代码，我认为它的时间复杂度是O(n^2)：

// 'Board'-class not included

val valueOfBoards: HashMap<Board, int>

fun cutBoard(b: Board, value: int) : int {

    if (b.isEmpty()) return 0
     if (valueOfBoards[b] > value) {
        return 0;
    } else {
        valueOfBoards[b] = value
    }

    int maxValue = Integer.MIN_VALUE

    for (Board piece : b.getPossiblePieces()) {
        val (cuttingCost, smallerBoard) = b.cutOffPiece(piece)
        val valueGained: int = piece.getPrice() - cuttingCost

        maxValue = Max(maxValue, valueGained + cutBoard(smallerBoard, value + valueGained))
    }

    return maxValue;
}

Board类的实现并不是简单的，这里有一些详细说明：

// returns all boards which fits in the current board
// for the initial board this will be width*height subboards
board.getPossiblePieces() 


// returns a smaller board and the cutting cost of the cut
// I can see this becoming complex, depends on how one chooses to represent the board.
board.cutOffPiece(piece: Board)

目前我还不清楚cutOffPiece()是否会破坏算法，因为你不知道如何最优地切割。我认为，由于算法将从大块到小块进行处理，所以在某个时候它会没问题。

我尝试通过将结果存储在类似于HashMap<Board, price>的东西中来解决子问题（相同的板子）的重新计算，并在继续之前将新板子与存储的最佳价格进行比较。

- Adam

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Prune · Accepted Answer

我用Python完成了这个算法，具体步骤如下：

best_val = 当前棋盘的值
检查每个水平和垂直的切割点是否可以获得更好的价值
- 对于切割点 <= 当前尺寸的一半（如果没有，则返回初始值）
- 在形成的两个棋盘上进行递归
- 如果值的总和 > best_val
- ... best_val = 这个总和
- ... 记录切割点和方向
返回结果：最佳值、切割点和方向

我不确定您需要什么样的返回值；我将最佳值和棋盘树返回了。对于您的第二个示例，这是：

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

带有调试跟踪的代码（缩进和标记的 打印）：

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)

针对两个测试的输出（利润和裁剪尺寸）：

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

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