我在一个在线编码挑战中遇到了这个问题。
给定一个长宽为（l，h）的盒子列表，输出包含所有盒子所需的最小堆栈数，假设您可以将一个盒子叠放在另一个盒子上，如果其长度和宽度小于其他盒子。
我无法想出多项式时间解决方案。 我已经构建了一个蛮力解决方案，递归地创建所有可能的堆栈排列（从N个堆栈开始。然后对于每个堆栈，尝试将其放在其他堆栈的顶部。然后递归生成给定新堆栈排列的所有堆栈可能性），然后返回所需的最小堆栈数。
我通过一些优化加速了它：
- 如果您可以将盒子A叠放在盒子B和盒子C上，并且您可以将盒子B叠放在盒子C上，则不考虑在盒子C上叠放盒子A。 - 记忆化堆栈排列，仅考虑堆栈的底部和顶部
以下是此解决方案的Python代码：
该算法可以在几秒钟内（1-3秒）解决一个16个盒子的问题，大约30秒内解决一个17个盒子的问题。我相信这是指数时间复杂度。（因为堆栈排列的数量呈指数级增长）
我相信有一种多项式时间复杂度的解决方案，但我不知道是什么。其中一个问题是备忘录需要依赖于当前的堆栈排列，这意味着你需要进行更多的计算。
给定一个长宽为（l，h）的盒子列表，输出包含所有盒子所需的最小堆栈数，假设您可以将一个盒子叠放在另一个盒子上，如果其长度和宽度小于其他盒子。
我无法想出多项式时间解决方案。 我已经构建了一个蛮力解决方案，递归地创建所有可能的堆栈排列（从N个堆栈开始。然后对于每个堆栈，尝试将其放在其他堆栈的顶部。然后递归生成给定新堆栈排列的所有堆栈可能性），然后返回所需的最小堆栈数。
我通过一些优化加速了它：
- 如果您可以将盒子A叠放在盒子B和盒子C上，并且您可以将盒子B叠放在盒子C上，则不考虑在盒子C上叠放盒子A。 - 记忆化堆栈排列，仅考虑堆栈的底部和顶部
以下是此解决方案的Python代码：
from time import time
def all_stacks(bottom, top, d={}):
memo_key = (tuple(bottom), tuple(top))
if memo_key in d:
# print "Using MEMO"
return d[memo_key]
res = len(bottom)
found = False
stack_possibilities = {}
# try to stack the smallest boxes in all the other boxes
for j, box1 in enumerate(bottom):
stack_possibilities[j] = []
for i, box2 in enumerate(top[j:]):
# box1 fits in box2
if fits(box2, box1):
stack_possibilities[j].append(i + j)
found = True
for fr, to_list in stack_possibilities.iteritems():
indices_to_keep = []
for box_ind in to_list:
keep = True
for box_ind_2 in to_list:
if fits(top[box_ind], top[box_ind_2]):
keep = False
if keep:
indices_to_keep.append(box_ind)
stack_possibilities[fr] = indices_to_keep
if found:
lens = []
for fr, to_list in stack_possibilities.iteritems():
# print fr
for to in to_list:
b = list(bottom)
t = list(top)
t[to] = t[fr]
del b[fr]
del t[fr]
lens.append(all_stacks(b, t, d))
res = min(lens)
d[memo_key] = res
return res
def stack_boxes_recursive(boxes):
boxes = sorted(boxes, key=lambda x: x[0] * x[1], reverse=False)
stacks = all_stacks(boxes, boxes)
return stacks
def fits(bigbox, smallbox):
b1 = smallbox[0] < bigbox[0]
b2 = smallbox[1] < bigbox[1]
return b1 and b2
def main():
n = int(raw_input())
boxes = []
for i in range(0,n):
l, w = raw_input().split()
boxes.append((long(l), long(w)))
start = time()
stacks = stack_boxes_recursive(boxes)
print time() - start
print stacks
if __name__ == '__main__':
main()
输入
17
9 15
64 20
26 46
30 51
74 76
53 20
66 92
90 71
31 93
75 59
24 39
99 40
13 56
95 50
3 82
43 68
2 50
输出：
33.7288980484
6
该算法可以在几秒钟内（1-3秒）解决一个16个盒子的问题，大约30秒内解决一个17个盒子的问题。我相信这是指数时间复杂度。（因为堆栈排列的数量呈指数级增长）
我相信有一种多项式时间复杂度的解决方案，但我不知道是什么。其中一个问题是备忘录需要依赖于当前的堆栈排列，这意味着你需要进行更多的计算。