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

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

给定具有长度和宽度(l，h)的盒子列表，请输出容纳所有盒子所需的最小堆叠数量，如果您可以将一个盒子的长度和宽度小于另一个盒子的宽度，则可以将一个盒子堆叠在另一个盒子的顶部。

我不知道如何提出多项式时间解决方案。我构建了一个蛮力解决方案，该解决方案以递归方式创建所有可能的堆栈排列(从N个堆栈开始。然后对于每个堆栈，尝试将其放置在另一个堆栈之上。然后在给出新堆栈排列的情况下递归生成所有堆栈可能性。)，然后返回所需的最小堆栈数。

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

如果可以将框A堆叠在框B和框C的顶部，并且可以将框B堆叠在框C的顶部，那么不要考虑将框A堆叠在框C的顶部。

仅考虑堆栈的最低和最高层emot堆栈安排

这是此解决方案的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()

输入

输出:

33.7288980484
6

该算法可在几秒钟(1-3)内解决16盒问题，在约30秒内解决17盒问题。我很确定这是指数时间。 (由于堆栈排列的数量成倍增加)。

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

最佳答案

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

现在我们需要找到该图的最小路径覆盖。这是一个标准问题，可以通过以下方式解决:

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

答案是盒数减去二部图中最大匹配项的大小。

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

关于python - 将箱子有效地堆叠到最少数量的堆叠中？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40223257/