Box Stacking Variation-Dynamic Programming

Question

Question 1: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.

Question 2: The above question was raised to 3 dimensions.

Question 3: The above question was then raised to k dimensions.

I believe we can apply dynamic programming to the above question.But

"A slab i can be put on slab j if both dimensions of i are less than that of j".

Not getting a clear idea on how to sort based on both the dimensions.

Answer 1

This is a Dynamic programming problem.

To solve this problem we need to figure out smaller sub-problem that solves larger set of problem. Let us say, Stack[i] indicate largest possible stack when input from 0 to i and this stack contains ith slab as its last slab. Then Stack[i] can be represented as:

if:AreaCover(Stack[j] > Stack[i])
    Stack[i] = Max{1 + Stack[j]} for all j [0 to i-1]

Here AreaCover is generic function which will return true (in all 3 questions) if a area condition is met.

Steps:

*Sort input as it is increasing on area.
*Build Stack[i] for all i [0 to n-1].
*Find Max value in Stack Array.

Answer 2

I don't think Dynamic Programming is necessary in this problem, here's my suggestion:

1. Create a graph G with a vertex set V- representing all the slabs, and no edges. ( O(|V|) )

2. For each pair of slabs i and j in V, check if one can be on top the other (compare any number of dimensions). Say slab i can be on top of slab j, add an edge i->j to the graph. If i and j are of the same dimensions, a single edge should be added. ( O(|V|^2) )

   The resulting graph is a DAG, since for any 3 slabs i,j,k , if i can be on top j, and j can be on top k, then k cannot be on top of i.

   In order to avoid cycles when 3 or more slabs are of the same size (e.g. i->j, j->k, k->i), if 2 slabs are of the same size, the direction of the edge will be from the smaller index to the larger (e.g. if i and j are equal in dimensions, then the edge we'll add is i->j)

3. Find the longest path in G. This path represent the stack with the maximum number of slabs.

   Finding such path in a DAG is an easy task and can be performed in linear time ( O(|V|+|E|) ).

The total running time of this algorithm is O(|V|) + O(|V|^2) + O(|V|+|E|) = O(|V|^2).