二维板切割算法

我的作业有问题。

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

考虑一个2 x 2价格矩阵板：

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 - (cost of cutting) 3x1 = 1
• 2水平的1x2 is worth 2x2 - (cost of cutting) 1x1 = 3
• 2垂直的1x2 is worth 3x2 - (cost of cutting) 1x1 = 5 -> 最佳最优利润
• 1水平的1x2 + 2 x (1x1) pieces is worth 2 + 2 - (cost of cutting) 2 = 2
• 1垂直的1x2 + 2 x (1x1) pieces is worth 3 + 2 - (cost of cutting) 2 = 3

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

我用 Python 做了这个。算法是

• best_val= 当前板的值
• check each horizontal and vertical cut for better value
  • 对于切点
  • 在形成的两个板上重复出现
  • 如果值的总和 >best_val
  • ... best_val=那个总和
  • ...记录切割点和方向
• 返回结果：best_val、切点、方向

我不确定您想要什么返回值；我归还了最好的价值和木板树。对于第二个例子，这是

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

代码，带有调试痕迹（indent和标记的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)

两个测试的输出（利润和切割尺寸）：

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

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