# Variant of the knapsack problem and box stacking

I'm facing a problem described as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h_i$, width $w_i$, depth $d_i$ and value $v_i$. You want to create a stack of boxes with a height limit $H$ and maximize the sum of the values, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each larger or equal than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. You are also allowed to use multiple instances of the same type of boxes.

I realized that it is a combination of the knapsack problem and the box stacking problem with small variations. I tried to solve it using the knapsack algorithm adding the box stacking restrictions, but I'm not getting the right results. Does anyone know a similar problem or could indicate me an algorithm? I have to implement it using dynamic programming.

• If you can use multiple instances of the same box, and we only require that the box below a box is larger than or equal to it, then you can get infinite value by picking any box with positive value and stacking an infinite number of copies of it on top of itself. Apr 22, 2018 at 16:18

Let $f(i)$ denote the maximum height that can be achieved if you have the $i$th box at the bottom. Can you find a recursive relation to let you compute $f$ in a recursive fashion?
Oops, you'll probably discover that doesn't quite seem to work. What additional information would we like to know about the box at the bottom, to enable you to find a recursive relation? You might need to add an extra parameter to $f$, so it becomes $f(i,\text{something})$ -- what should you put as the "something"?