Stacking box

Given a list of three values, height, width and length, create a stack of boxes that is as tall as possible. A box can be stacked on top of another box if dimensions of its 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. A box can stack in any orientation and multiple instances of the same type of box is allowed.

Hint

Building upon understanding of Stacking box (Memoization). Pay attention to the cache. Tabulation essentially reconstructs the cache.

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

• Python
• Javascript
•  Run

def stack(boxes):
  cache = [0] * len(boxes)

  mx = 0
    
  for i in range(len(boxes) - 1, -1, -1):
    cache[i] = boxes[i][2]
    
    for j in range(i + 1, len(boxes)):
      if boxes[i][0] > boxes[j][0] and boxes[i][1] > boxes[j][1]:
        cache[i] = max(cache[i], boxes[i][2] + cache[j])
    
    mx = max(mx, cache[i])
  
  return mx

data = [[4, 6, 7], [1, 2, 3], [4, 5, 6], [10, 12, 32]]
boxes = []

for x in data:
  a = x[0]
  b = x[1]
  c = x[2]

  boxes.append([a, b, c])
  boxes.append([a, c, b])
  boxes.append([b, a, c])
  boxes.append([b, c, a])
  boxes.append([c, a, b])
  boxes.append([c, b, a])

boxes.sort(key = lambda a: (a[0], a[1]), reverse = True)

print(stack(boxes))

function stack(boxes) {
  const cache = Array(boxes.length).fill(0);

  let max = 0;

  for (let i = boxes.length - 1; i >= 0; i--) {
    cache[i] = boxes[i][2];
    
    for (let j = i + 1; j < boxes.length; j++) {
      if (boxes[i][0] > boxes[j][0] && boxes[i][1] > boxes[j][1]) {
        cache[i] = Math.max(cache[i], boxes[i][2] + cache[j]);
      }
    }
    
    max = Math.max(max, cache[i]);
  }

  return max;
}

const data = [[4, 6, 7], [1, 2, 3], [4, 5, 6], [10, 12, 32]];
const boxes = data
  .reduce((cum, i) => {
    const a = i[0];
    const b = i[1];
    const c = i[2];

    cum.push([a, b, c]);
    cum.push([a, c, b]);
    cum.push([b, a, c]);
    cum.push([b, c, a]);
    cum.push([c, a, b]);
    cum.push([c, b, a]);

    return cum;
  }, [])
  .sort((a, b) => (a[0] == b[0]) ? (b[1] - a[1]) : b[0] - a[0]);

console.log(stack(boxes, 0));