algorithm - 二维板的切割算法

Question

我的作业有问题。

给定一 block 尺寸为 m x n 的木板，将这 block 木板切成总价最优的矩形 block 。一个矩阵给出了从原始的、未切割的电路板到每个可能的电路板尺寸的价格。

考虑一个带有价格矩阵的 2 x 2 棋盘:

3 4

3 6

例如 1，每次切割的成本都是固定的。
一 block 长度1 x 1 值3。
水平长度 1 x 2 值 4。
垂直长度 1 x 2 的长度等于 3。
整盘值(value)6。

对于这个例子，最佳利润是 9，因为我们将棋盘切成 1 x 1 block 。每件作品值(value) 3，我们切割了 3，所以 4 x 3 - 3 x 1 = 9。

第二个例子:

1 2

3 4

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

• 4 1x1 件值(value) 4x1 -(切割成本)3x1 = 1
• 2 水平 1x2 等于 2x2 -(切割成本)1x1 = 3
• 2 垂直 1x2 等于 3x2 -(切割成本)1x1 = 5 -> 最佳利润
• 1 水平 1x2 + 2 x (1x1) 件值(value) 2 + 2 -(切割成本)2 = 2
• 1 垂直 1x2 + 2 x (1x1) 件值(value) 3 + 2 -(切割成本)2 = 3

我已经阅读了很多关于杆切割算法的内容，但我不知道如何解决这个问题。你有什么想法吗？

Answer 1

我是用 Python 做的。该算法是

• best_val = 当前棋盘值
• 检查每个水平和垂直切割以获得更好的值(value)
  • 对于切点 <= 当前维度的一半(如果没有，返回初始值)
  • 重复组建的两个委员会
  • 如果值的总和 > best_val
  • ... best_val = 总和
  • ...记录切割点和方向
• 返回结果:best_val、切点、方向

我不确定您需要什么返回值；我把最好的值(value)和木板树还给了我。对于你的第二个例子，这是

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

代码，带有调试痕迹(缩进 和标记的print):

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]])