1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 22 '18 at 16:18
2
$\begingroup$

This is a good dynamic programming exercise. Here's a hint.

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?

Think about that one. If you get stuck, here's another hint:

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"?

If you can answer those hints, you should be very close to finding a dynamic programming algorithm for the problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.