将箱子有效地堆叠到最少数量的堆叠中？ [英] Stacking boxes into fewest number of stacks efficiently?

问题描述

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

I got this question in an online coding challenge.

给出一个具有长度和宽度（l，h）的盒子列表，输出所需的最小堆叠数量可以容纳所有盒子，假设您可以将一个盒子的长度和宽度小于另一个盒子的长度。

Given a list of boxes with length and widths (l, h), output the minimum number of stacks needed to contain all boxes, given that you can stack one box on top of another if its length and width are less than the other box's.

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

I can't figure out how to come up with a polynomial time solution. I've built a brute force solution that creates all possible stack arrangements recursively (start with N stacks. Then for each stack, try putting it on top of each other stack. Then recursively generate all stack possibilities given the new stack arrangement.), and then returns the smallest number of stacks needed.

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

I've sped it up with a few optimizations:

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


• 记住堆栈排列，只考虑堆栈的底部和顶部

这里是python代码此解决方案：

Here's the python code for this solution:

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盒问题。我很确定这是指数时间。 （因为堆栈排列的数量成倍增加。）

The algorithm solves a 16 box problem in a few seconds (1-3), a 17 box problem in ~30 seconds. I'm pretty sure this is exponential time. (Since there's an exponential number of stack arrangements).

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

I'm pretty sure there's a polynomial time solution, but I don't know what it is. One of the issues is that memoization depends on the current stack arrangements, meaning you have to do more computations.

推荐答案

让我们构建一个图，其中每个框都有一个顶点，并且如果A可以堆叠在B的顶部，则从框A到框B的边都存在。该图是非循环的（因为可以堆叠在顶部是传递关系，并且可以装箱不能堆叠在其自身之上）。

Let's build a graph, where there is vertex for each box and an edge from a box A to a box B if A can be stacked on top of B. This graph is acyclic (because "can stack on top" is a transitive relation and a boxed can't stacked on top of itself).

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

Now we need to find the minimum path cover of this graph. It's a standard problem and it's solved this way:

1. 让我们建立一个二部图（原始图中的每个顶点得到两个副本）。对于原始图中的每个 A-> B 边，在 A 的左副本和 B 的正确副本。

1. Let's build a bipartite graph (each vertex in the original graph gets two "copies" in the left and the right part). For each A->B edge in the original graph, there is an edge between the left copy of A and the right copy of B.

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

The answer is number of boxes minus the size of the maximum matching in the bipartite graph.

二部图为 O（n）顶点和 O（n ^ 2）边。例如，如果使用库恩算法查找匹配项，则总时间复杂度为 O（n ^ 3），其中 n 是盒子的数量。

The bipartite graph as O(n) vertices and O(n^2) edges. If we use, for instance, Kuhn's algorithm to find a matching, the total time complexity is O(n^3), where n is the number of boxes.

这篇关于将箱子有效地堆叠到最少数量的堆叠中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！