BoxTower | Topcoder Archive

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

```
{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.
```
{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.
```
{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.
```
{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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.