BagPacking | Topcoder Archive

Problem Statement

Bob's exams are over and he wants to go home on his summer vacation. Bob has some bags and wants to send them home. You are given sizes of the bags in int[] bagsizes.

A bag of size x can fit inside a bag of size y, if y is strictly greater than x. The courier service charges based on the number of bags, so it is in Bob's best interest to nest bags inside of each other as efficiently as possible. Note that only a single bag of size less than y can fit inside a bag of size y. However, the smaller bag may have a still smaller bag inside of it, and so on.

Return the minimum number of bags Bob must pay for, assuming he packs them inside each other optimally.

Definition

Class:: BagPacking
Method:: minPay
Parameters:: int[]
Returns:: int
Method signature:: int minPay(int[] bagsizes)
(be sure your method is public)

Constraints

Number of elements in bagsizes will be between 1 and 50, inclusive.
Each element of bagsizes will be between 1 and 100, inclusive.

Examples

```
{1, 2, 3}
```
```
Returns: 1
```
You can pack all the bags into a single bag. Pack the bag of size 1 inside the bag of size 2, then pack that bag into the bag of size 3. Overall, you will just send the bag of size 3, and pay for a single bag.
```
{4, 3, 4}
```
```
Returns: 2
```
You can pack the bag of size 3 into one of the bags of size 4. The other bag of size 4 will remain separate. So, two bags in total.
```
{3,3,3,3,1}
```
```
Returns: 4
```
```
{3,1,3,2,4,3,3}
```
```
Returns: 4
```

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.