Box stacking problem

by

I think you can solve this using the dynamic programming longest increasing subsequence algorithm: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Accounting for the rotations is easy enough: for every tower all you have to check is what happens if you use its height as the length of the base and its width as the height and what happens if you use it in the natural way. For example:

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

Becomes something like (yeah, I know it looks nothing like it should, just follow the notations): 

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

So for each block you actually have 3 blocks representing its possible rotations. Adjust your blocks array according to this, then sort by decreasing base area and just apply the DP LIS algorithm to the get the maximum height.

The adapted recurrence is: D[i] = maximum height we can obtain if the last tower must be i.

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

See a video explaning this here: http://people.csail.mit.edu/bdean/6.046/dp/

More Related Contents:

  1. How to determine the longest increasing subsequence using dynamic programming?
  2. Subset Sum algorithm
  3. What is dynamic programming? [closed]
  4. Getting the submatrix with maximum sum?
  5. how to find longest palindromic subsequence?
  6. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  7. How to count integers between large A and B with a certain property?
  8. How to understand the dynamic programming solution in linear partitioning?
  9. Maximum Contiguous Subsequence Sum of At Least Length L
  10. 3-PARTITION problem
  11. How do I create a URL shortener? [closed]
  12. How do I calculate a point on a circle’s circumference?
  13. Algorithm for Additive Color Mixing for RGB Values
  14. Algorithm to generate all possible permutations of a list?
  15. Fast permutation -> number -> permutation mapping algorithms
  16. Algorithm to detect intersection of two rectangles?
  17. An efficient compression algorithm for short text strings [closed]
  18. How to detect the BPM of a song in php [closed]
  19. Find the shortest path in a graph which visits certain nodes
  20. Algorithm to separate items of the same type
  21. how to calculate binary search complexity
  22. Combined area of overlapping circles
  23. Quick Sort Vs Merge Sort [duplicate]
  24. insert, delete, max in O(1)
  25. How Can I Best Guess the Encoding when the BOM (Byte Order Mark) is Missing?
  26. Easiest algorithm of Voronoi diagram to implement? [closed]
  27. “Rounding” colour values to the nearest of a small set of colours
  28. Color gradient algorithm
  29. When is each sorting algorithm used? [closed]
  30. Binary tree level order traversal

Leave a Comment