我用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 = []
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
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
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]])