有效地将盒子堆叠成最少数量的堆叠？

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

该算法在几秒钟内解决了一个16箱问题（1-3），在约30秒内解决了17箱问题。我很确定这是指数时间。（因为堆叠排列的数量是指数级的）。

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

Answer 1

这一开始看起来很简单，但是考虑到各种可能性，很快就变成了一个难题。然而，我已经成功地用JS实现了我的算法，我对此很有信心，而且JS有一些特性，比如对象是引用类型，这在这个特殊的例子中对我帮助很大。

我从假设开始，我们可以转动盒子，让它们的长边在x轴上。然后给定的17个盒子在Chrome中在4~10毫秒之间完成，在FF中在15~25毫秒之间完成，结果总共最少5个盒子可以包含所有17个盒子。

此外，我尝试了50盒盒子（每个盒子的随机尺寸在1-100之间）。因此，50盒机箱，取决于它们的安装方式，在Chrome和FF中都以令人难以置信的250〜15000毫秒的速度解决。我想70岁是这份工作在变得非常无聊之前的限制。

代码在速度上仍然可以提高，但到目前为止是这样的。一旦我有空闲时间，我将尝试在一两天内对代码进行详细描述。

js lang-js prettyprint-override">function insertBoxes(data){
  if (data.length <= 1) return data[0] ? [data] : data;

  function flatMap(o){
    return o.inside.length ? o.inside.reduce((p,b) => p.concat(flatMap(b).map(f => f.concat(o.id))),[])
                           : [[o.id]];
  }

  function getBest(arr, r = []){
    var i = arr.findIndex(a => a.every(i => !used[i])),len,tgt,bests,best;
    if (i === -1) return r;
      len = arr[i].length;
      tgt = arr.slice(i);
    bests = tgt.filter(a => a.length === len && a.every(x => !used[x]));
     best = bests.map((a,i) => [a.reduceRight((p,c) => p + boxes[c].x + boxes[c].y, 0), i])
                 .reduce((p,c) => c[0] < p[0] ? c : p,[Infinity,-1]);
    bests[best[1]].forEach(i => used[i] = true);
    r.push(bests[best[1]]);
    return getBest(tgt,r);
  }

  var boxes = data.map((e,i) => ({id:i, x:Math.max(e[0],e[1]), y:Math.min(e[0],e[1]), inside:[]})),
       used = Array(data.length).fill(false),
    interim = boxes.map((b,_,a) => { a.forEach(box => (b.x > box.x && b.y > box.y) && b.inside.push(box));
                                     return b;
                                   })
                   .map(b => flatMap(b))
                   .reduce((p,c) => p.concat(c))
                   .sort((a,b) => b.length-a.length);
  return getBest(interim).map(b => b.map(i => data[i]))
                         .concat(insertBoxes(data.reduce((p,c,i) => used[i] ? p : (p.push(c),p) ,[])));
}

var input = [[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]];
   result = [],
       ps = 0,
       pe = 0,
ps = performance.now();
result = insertBoxes(input);
pe = performance.now();
console.log("boxing", input.length, "boxes done in:", pe-ps,"msecs and all boxes fit in just", result.length,"boxes");
console.log(JSON.stringify(result));

Answer 2

我最近也遇到了这个问题。我提出以下 O（NlogN） 解决方案：

1)维护所有正在使用的当前盒子堆栈的最顶层盒子的列表AllStkTops。它将被初始化为一个空列表。

2)按照盒子长度的降序排列。(如果长度相等，则按照宽度的递增(是的，不是递减)顺序对它们进行排序)。

3）开始挑选盒子（从最长的盒子开始）并将它们放在当前的堆栈之一中。对于第一个盒子，将没有堆栈，因此它将是第一个盒子堆栈的基础。第二个盒子要么转到第一个盒子的顶部，要么是第二个堆栈的底部。随着我们继续这个过程，我们会意识到，对于手头的任何盒子，它的长度都将小于或等于所有堆栈中最上面的盒子。因此，我们只需要担心广度。从第一个堆栈开始，使用所有当前堆栈的顶部检查其宽度，并将其放在堆栈的顶部，该堆栈将具有i）长度和宽度严格大于当前框的长度和宽度，以及ii）最小可能的宽度（为最佳性）。如果所有堆栈都无法容纳此框，请创建一个以此框为基数的新堆栈。

请注意，所有堆叠顶部的宽度将按增加的顺序排列，因为我们仅在该时间点的框的宽度大于所有堆叠顶部时才会创建新堆栈。（对于等长框的情况，我们在排序时已经将它们按宽度递增的顺序排列）。因此，我们可以使用二进制搜索过程来查找具有足够大宽度的最窄堆栈顶部。但是我们还需要确保它的长度严格大于（而不仅仅是等于）给定盒子的长度。但是，我声称顶部的长度永远不会成为问题，因为
i）盒子是按长度的递减顺序挑选的，因此顶部的长度不能严格地小于，并且ii）它也可能是不相等的，因为我们已经按照宽度的增加顺序对长度相等的盒子进行了排序， 因此，获得前一个盒子的堆栈必须朝向此堆栈顶部的左侧。

因此，我们可以使用二进制搜索过程来查找当前框的最佳堆栈顶部。

我们可以重复上述过程，直到将所有盒子放在堆栈中。最后，计算所有StkTops中的堆栈数。

这在复杂度上是O（NlogN），因为排序需要O（NlogN）时间，而对每个框进行二进制搜索需要O（logN）时间。

我愿意回答别人在我的算法中发现的任何问题和/或缺陷。

干杯

Answer 3

让我们建立一个图，其中每个盒子都有一个顶点，如果A可以堆叠在B的顶部，则有一条从盒子A到盒子B的边，这个图是无环的(因为“可以堆叠在顶部”是传递关系，并且一个盒装的不能堆叠在自己的顶部)。

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

>

让我们构建一个二分图（原始图中的每个顶点在左侧和右侧部分获得两个“副本”）。对于每个 A-

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

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