PackingContainers | Topcoder Archive

Problem Statement

You have a collection of containers. They each have the same shape but they may have different sizes. The volumes of the individual containers you have are given in the int[] volume.

You want to store all your containers in a closet. Before you do that, you can compress your collection by placing some containers into others. A container can be placed into another, bigger container if the volume of the bigger container exceeds the volume of the smaller container by at least 10.

You are allowed to nest containers, e.g. by putting A into B and then B into C. However, you are not allowed to place two or more smaller containers directly into the same bigger container next to each other (to prevent scraping).

Compute and return the minimum total volume the packed containers can take in the closet.

Definition

Class:: PackingContainers
Method:: pack
Parameters:: int[]
Returns:: int
Method signature:: int pack(int[] volume)
(be sure your method is public)

Constraints

volume will contain between 1 and 50 elements, inclusive.
Each element of volume will be between 1 and 1,000,000, inclusive.

Examples

```
{10, 50, 20, 40, 30}
```
```
Returns: 50
```
You can nest all these containers: the smallest one goes into the second smallest, and so on. This means that they will all end inside the biggest container, and the volume taken in the closet is therefore only 50.
```
{9, 18, 27, 36, 45}
```
```
Returns: 81
```
The best way to pack these containers is to: Put the one with volume 9 into the one with volume 27 and then put that one into the biggest one. Also put the one with volume 18 into the one with volume 36. The total volume the packed containers will then take in your closet will be 36 + 45 = 81.
```
{100, 50, 100, 50, 50, 100}
```
```
Returns: 300
```
Each of the small containers goes into one of the big containers.
```
{48, 100, 49, 100, 50, 100, 51}
```
```
Returns: 348
```
Too many small containers, one of them will remain outside. The optimal choice is obviously to leave the smallest one outside.

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.