1

Given a set of 24 boxes with varying heights. How can one optimally stack the boxes into 3 columns, with the least difference in column height.

  • The width of all boxes is equal.
  • The # of boxes in each column does not have to be equal.
  • Best case scenario the boxes maintain a close relation to this order...

123
456
789
etc

wdm
  • 111
  • I don't know what 123 456 789 etc means. Is it some attempt to tells us the heights of the boxes? Without knowing the heights, it would seem to be difficult to answer the question. Even knowing the heights, problems of this type are (in general) believed to be very difficult to solve; the "subset sum" problem is NP-complete. – Gerry Myerson Feb 09 '13 at 05:00
  • #1 would be the first number in the set and the top of the first column. A set of varying heights may look like this [600, 650, 545, 822, etc]. – wdm Feb 09 '13 at 22:44
  • If the varying heights have no clear pattern, the problem can be very hard. As suggested, check out the subset sum problem and/or the set partition(ing) problem. – Gerry Myerson Feb 09 '13 at 23:02

2 Answers2

1

if you can short all the boxes in ascending order of Height, then you can arrange the boxes as

1 - 2 - 3
6 - 5 - 4
7 - 8 - 9
12-11 -10

this will give you least difference in column height.

user60878
  • 79
0

This is similar to the subset sum problem. If you required the same number of boxes in each column, you could subtract that from the height of each box and be there. The usual approach is to find a transformation of box heights to sets that is soluble iff the usual subset sum is soluble, then declare it hard and quit.

Ross Millikan
  • 374,822