Is folding boxes into the least number of stacks efficient?

Question

I got this question in online programming.

Given the list of boxes with length and width (l, h), print the minimum number of stacks needed to accommodate all boxes, given that you can stack one square on top of another if its length and width are less than other boxes.

I cannot figure out how to find a solution with polynomial time. I built a brute-force solution that recursively solves all possible stack layouts (start with N stacks, and then for each stack try placing it on top of every other stack and then recursively generate all the stack features based on the new stack layout.), And then returns the smallest number of stacks needed.

I accelerated it with a few optimizations:

• If you can stack box A on top of box B and in box C, and you can stack box B at the top of box C, then don't look at the box for stacking A on box C.
• Remember the stack layout, considering only the lower and upper levels of the stacks.

Here is 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() 

Enter

 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 

Output:

 33.7288980484 6 

Within a few seconds (1-3), the algorithm solves the problem with a short box (16), the problem with field 17 - after 30 seconds. I am sure this is an exponential time. (Since there is an exponential stack layout number).

I am sure that there is a polynomial time solution, but I do not know what it is. One problem is that memoization depends on existing stack mechanisms, i.e. you need to do more calculations.

Answer 1

Let's build a graph where for each field there is a vertex and an edge from field A to field B, if A can be laid on top of B. This graph is acyclic (because "can stack on top" is a transition relation and the box cannot stack on top).

Now we need to find the minimum coverage of the path of this graph. This is a standard problem, and it was solved like this:

• Let's build a bipartite graph (each vertex in the original graph gets two “copies” on the left and right sides). For each edge A->B in the original graph there is a left copy of A and a right copy of B

• The answer is the number of cells minus the size of the maximum match in the bipartite graph.

Two-sided graph as O(n) vertices and O(n^2) edges. If we use, for example, the Kuhn algorithm for matching, the total time complexity is O(n^3) , where n is the number of boxes.

Answer 2

I recently came across this question. I suggest the following O (NlogN) solution:

1) Keep a list of AllStkTops from the very top window of all the current block stacks that are used. It will be initialized with an empty list.

2) Sort the boxes in descending order of their length. (if the lengths are equal, then sort them in ascending (yes, without decreasing) order of latitudes).

3) Start collecting boxes (starting with the longest) and place them on one of the current stacks. There will be no stacks for the first window, so this will be the basis of the first stack. The second box will either go to the top of the first window, or will be the basis of the second stack. When we continue this process, we will understand that for any box in the hand, its length will be less than or equal to the topmost box of all the stacks. Therefore, we only need to worry about latitude. Check its width with the vertices of all current stacks, starting from the first stack, and put it on the top of the stack, which will have: i) the length and width are strictly greater than the current block, and ii) the minimum possible width (for optimality). If none of the stacks can place this field, create a new stack with this field as a base.

Please note that the width of all the top stacks will be in increasing order, since we only create a new stack when the width of this window is greater than all the vertices of the stack at this point in time. (In the case of boxes of equal length, we already had them in increasing order of width when sorting). Therefore, we can use the binary search procedure to find the narrowest top of the stack, which would have a sufficiently large width. But we also need to make sure that its length is strictly greater (and not only equal) than its size. However, I argue that vertex length will never be a problem because
i) The boxes are selected in decreasing order of length, so the top length cannot be strictly less, and ii) It also cannot be equal, because we already sorted the rectangles with the same length in increasing order of their width, so the stack that the previous box received should have been to the left of the top of this stack.

Therefore, we can use the binary search procedure to find the optimal stack top for the current field.

We can repeat the procedure described above until we put all the boxes in the stacks. At the end, count the number of stacks in AllStkTops.

This is the complexity of O (NlogN) in complexity, since sorting takes O (NlogN), and a binary search for each window takes O (logN).

I would like to answer any questions and / or shortcomings that someone found in my algorithm.

Hooray!

Answer 3

At first it looked simple, but given the possibilities, it quickly turned out to be difficult. Nevertheless, I managed to implement my algorithm in JS, where I feel very confident, plus JS have features such as objects that are reference types, which helped me a lot in this particular case.

I start with the assumption that we can rotate the boxes so that their longer side is on the x axis. Then the data of 17 boxes is executed between 4 ~ 10 ms in Chrome and 15-25 ms in FF, as a result, at least 5 cells can contain all 17.

In addition, I tried 50 cases of boxes (each with random sizes from 1 to 100). Thus, 50 boxes, depending on how they fit, are allowed between the unbelievable 250 ~ 15,000 ms in both Chrome and FF. I think 70 is the limit for this job before it gets really boring.

The code can still be augmented in terms of speed, but at the moment it is. I will try to make a detailed description of the code in a day or two, when I have free time.

 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 => (bx > box.x && by > 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)); 

Note. The code above uses a recursive top-down approach, but I began to think that a lower-level dynamic programming approach would be a real solution to this problem.

OK, as I thought the dynamic programming approach leads to a much faster solution. I do not delete the above, but please do not pay attention to it.

The following code will allow an array of cells of 17 elements in an array of less than 1 ms, 1000 elements in less than 100 ms.

 function boxBoxes(d){ return d.sort((a,b) => b[0]*b[1] - a[0]*a[1]) .map(b => b[0] < b[1] ? b : [b[1],b[0]]) .map(function(b,i,a){ bc = i ? a.slice(0,i) .filter(f => f[0] > b[0] && f[1] > b[1]).length || Infinity : Infinity; return [b]; }) .sort((a,b) => b[0].c - a[0].c) .reduceRight(function(p,c,i,a){ var r = a.filter(f => f[f.length-1][0] > c[0][0] && f[f.length-1][1] > c[0][1]); r.length && r[0].push(...a.splice(i,1)[0]); return a; },void 0); } var data = [[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 = boxBoxes(data); console.log(result.length,"boxes:",JSON.stringify(result));