I’m facing a variation of the box stacking problem, the usual box stacking problem is described here: Dynamic Programming - Box Stacking Problem
In the variant, the problem is determining the maximal height that can be achieved with the additional constraint that each box can be picked at most k times.
I’m stuck, can anyone help me out? How would you approach this problem?
I can think of a n*k solution where I declare another parameter k for the recursive function! If a box is picked, it’s k will decrease by 1. When k = 0, we can’t take more. The remaining solution stays the same.
Correct me if I’m wrong, I don’t think ‘k’ is relevant here because, every box has 3 possible orientations, and once one of its orientations is placed in the stack at some position, you cannot have the same orientation anywhere else in the stack (because the dimensions of the base must both be strictly decreasing). So, you will never use more than 3 duplicates of a box, actually, I don’t think even 3 is possible, the most that you can have is 2.
@hemanth_1 You are right, there is no way a box can be picked more than two times because 2 of the possible orientations must have their longest dimension equal and since box A can be stacked on another box B if and only if A can be rotated such that both of its dimensions are strictly less than the dimensions of box B only one of the 2 orientations with their longest dimension being equal can be picked.
So all cases where k >= 2 are equivalent to the traditional box stacking problem. Since k > 0 (k=0 is trivial) the only case left is k = 1 (either pick a box or don’t). Nice observation!