TopCoder problem "BoxTower" used in SRM 310 (Division I Level Three)



Problem Statement

    

You have N boxes of various sizes. You would like to stack some of them upon each other to create a tower that's as tall as possible.

When building the tower, you are allowed to reorder and rotate the boxes. However, the tower must obey the following rules:

  • The tower must be constructed by repeatedly taking an unused box and placing it on top of the current tower.
  • Each box must have sides parallel to the sides of the bottommost box.
  • If a box A is placed on box B, then the entire bottom side of A must be placed on the top side of B. In other words, no part of the bottom side of A may overhang the top side of B.

You are given the dimensions of the boxes as three int[]s x, y, and z. The i-th elements in x, y, and z specify the dimensions of the i-th box. Return an int giving the height of the tallest tower that can be constructed using the above rules.

 

Definition

    
Class:BoxTower
Method:tallestTower
Parameters:int[], int[], int[]
Returns:int
Method signature:int tallestTower(int[] x, int[] y, int[] z)
(be sure your method is public)
    
 

Notes

-If the bottom side of one box is equal to the top side of another box, they may be placed atop each other.
 

Constraints

-x will contain between 1 and 15 elements, inclusive.
-x, y, and z will contain the same number of elements.
-Each element in x, y, and z will be between 1 and 10,000,000, inclusive.
 

Examples

0)
    
{10, 50, 40, 20, 30}
{10, 50, 40, 20, 30}
{10, 50, 40, 20, 30}
Returns: 150
All five boxes are cubes of different sizes. They can all be used to build a tower.
1)
    
{20, 30}
{20, 30}
{20, 10}
Returns: 30
This time we have two boxes: a 20x20x20 cube, and a 30x30x10 slab. The best solution is to place the slab on its largest side, and then to put the cube on the top of it.
2)
    
{20, 30}
{20, 33}
{20, 10}
Returns: 33
Now the slab is a bit longer, and the best solution is to use only the slab, standing on its 10x30 side.
3)
    
{100, 100}
{10, 12}
{10, 8}
Returns: 110
Note that if both boxes are rotated so that their height is 100, neither can be placed on top of the other.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6576

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9990&pm=6576

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Brute Force, Dynamic Programming, Sorting