python - 有效地将箱子堆叠成最少数量的堆叠？

Question

我在在线编码挑战中得到了这个问题。

给定一个长度和宽度为 (l, h) 的盒子列表，输出包含所有盒子所需的最小堆叠数，前提是如果一个盒子的长度和宽度小于其他盒子的。

我不知道如何提出多项式时间解决方案。我已经构建了一个蛮力解决方案，它递归地创建所有可能的堆栈排列(从 N 个堆栈开始。然后对于每个堆栈，尝试将它放在其他堆栈的顶部。然后递归地生成所有可能的堆栈排列给定新的堆栈排列。)，然后返回所需的最小堆栈数。

我通过一些优化加快了速度:

• 如果您可以将盒子 A 堆叠在盒子 B 和盒子 C 的顶部，并且您可以将盒子 B 堆叠在盒子 C 的顶部，那么请不要考虑将盒子 A 堆叠在盒子 C 上。
• 内存堆栈排列，只考虑堆栈的底层和顶层

这是此解决方案的 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 盒问题。我很确定这是指数时间。 (因为堆栈排列呈指数级增长)。

我很确定存在多项式时间解，但我不知道它是什么。其中一个问题是记忆化取决于当前的堆栈安排，这意味着您必须进行更多计算。

Answer 1

让我们构建一个图，其中每个框都有一个顶点，如果 A 可以堆叠在 B 的顶部，则有一条从框 A 到框 B 的边。该图是非循环的(因为“可以堆叠在顶部”是一个传递关系和盒装不能堆叠在自身之上)。

现在我们需要找到这个图的最小路径覆盖。这是一个标准问题，它是这样解决的:

1. 让我们构建一个二部图(原始图中的每个顶点在左侧和右侧部分都有两个“副本”)。对于每个 A->B原始图中的边，A 的左副本之间有一条边和B的正确副本.

2. 答案是框数减去二分图中最大匹配的大小。

二分图为O(n)顶点和O(n^2)边缘。例如，如果我们使用 Kuhn 的算法来查找匹配项，则总时间复杂度为 O(n^3) , 其中n是盒子的数量。