Example: Box Stacking - rFronteddu/general_wiki GitHub Wiki
You are given boxes of different WxLxH and are tasked of stacking as many as you can with the caveat that a box must have strictly smaller W and L than boxes they sit on.
- Consider 1,2,4 and 3,2,5
- first we consider all rotations:
| --- |
W |
L |
H |
| --- |
4 |
2 |
1 |
| --- |
4 |
1 |
2 |
| --- |
2 |
1 |
4 |
| --- |
5 |
3 |
2 |
| --- |
5 |
2 |
3 |
| --- |
3 |
2 |
5 |
- Next we sort them by base area
| --- |
W |
L |
H |
WxL |
| 0 |
5 |
3 |
2 |
15 |
| 1 |
5 |
2 |
3 |
10 |
| 2 |
4 |
2 |
1 |
8 |
| 3 |
3 |
2 |
5 |
6 |
| 4 |
4 |
1 |
2 |
4 |
| 5 |
2 |
1 |
4 |
2 |
Next we populate 2 arrays, the first one we keep track of the max h, the second the index of the previous box
- we set i = 1 and j = 0, we observe that i cannot go on top of i so nothing changes
- we set i = 2 and j = 0, we test all j to see which gives the best max h, we observe that we can stack on top of 0 but not on top of 1
- we set i = 3 and j = 0, we test all j
- We find the maximum index and we backtrack to find the boxes
// each x[0] = (w,l,h)
boxStacking(x)
n = x.len - 1
y = []
for i = 0 to n-1
// note that WxL == LxW
y.add((x[i, 0], x[i, 1], x[i, 2]))
y.add((x[i, 2], x[i, 1], x[i, 0]))
y.add((x[i, 2], x[i, 0], x[i, 1]))
// sort by LxW
y.sort(el -> el[0] * el[1])
sum = [0..y.len-1]
step = [0..y.len-1]
for i = 0 to y.len-1
sum[i] = y[i,2]
step[i] = i
maxI = 0
for i = 1 to y.len-1
for j = 0 to i - 1
// can box i stack on box j?
if y[i,0] < y[j,0] && y[i,1] < y[j,1]
// yes
q = x[i,2] + sum[j]
if q > sum[i]
sum[i] = q
step[i] = j
if sum[maxI] < sum[i]
maxI = i
print("Max h is : " + sum[maxI])
print("Boxes:")
while(true) {
print(maxI)
if maxI == step[maxI]
break
maxI = step[maxI]
}