二维板切割算法 [英] Cutting algorithm of two dimensional board

问题描述

我的作业有问题。

给出一个尺寸为 m x n 的木板给定的价格，将此板切成具有最佳总价的矩形块。矩阵给出了每种尺寸的价格（通过原始的未切割板）。

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.

考虑 2 x 2 带有价格矩阵的板子：

Consider a 2 x 2 board with the price matrix:

3 4

3 6

我们每次切割都有恒定的成本，例如 1 。

长度为 1 x 1 的片段的价值为 3 。

水平长度 1 x 2 的价值为 4 。

长度为 1 x 2 的垂直片段的价值为 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.

在此示例中，最优利润是9 ，因为我们将木板切成 1 x 1 块。每块价值 3 ，我们削减了 3 ，所以 4 x 3 - 3 x 1 = 9 。

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.

第二个示例：

1 2

3 4

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

Now I have to consider all the solutions:

• 4 1x1 件价值 4x1-（切割成本）3x1 = 1


• 2 水平 1x2相当于2x2-（切割成本）1x1 = 3


• 2 垂直 1x2相当于3x2-（切割成本） 1x1 = 5 ->最佳最优利润


• 1 水平 1x2 + 2 x（1x1）件值得2 + 2-（切割成本）2 = 2


• 1 垂直 1x2 + 2 x（1x1）件价值3 + 2-（切割成本）2 = 3

• 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?

推荐答案

我是在Python中完成的。算法为

I did this in Python. The algorithm is

• best_val =当前板的价值


• 检查每个水平和垂直切割的值是否更好
  
  
  
  
  • 切割点< =当前尺寸的一半（如果没有，则返回初始值）
  
  
  • 在形成的两个板上重复出现
  
  
  • 如果值的总和> best_val
  
  
  • ... best_val =该金额
  
  
  • ...记录切割点和方向
  
  
  • 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

    我不确定您想要返回值是什么；我退还了最有价值的东西和木板。对于第二个示例，这是

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

    代码，并带有调试痕迹（ indent 和带有标签的 print s）：

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

    这篇关于二维板切割算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！