ClassicProblem | Topcoder Archive

Problem Statement

This task is about a classic problem in computer science: the knapsack problem.

There are n types of items. The types are numbered 0 through n-1, inclusive. For each valid i, you have cnt[i] items of type i, and each of these items has weight w[i] and value v[i]. You are given the int[]s cnt, w, and v. You are also given an int limit.

Find a subset of the available items such that:

the total weight of the selected items is smaller than or equal to limit
the total value of the selected items is as large as possible

Return the total value of the selected items.

Definition

Class:: ClassicProblem
Method:: maximalValue
Parameters:: int[], int[], int[], int
Returns:: long
Method signature:: long maximalValue(int[] cnt, int[] w, int[] v, int limit)
(be sure your method is public)

Constraints

cnt will contain between 1 and 80 elements, inclusive.
cnt, w and v will contain the same number of elements.
Each element in cnt will be between 1 and 1,000,000,000, inclusive.
Each element in w will be between 1 and 80, inclusive.
Each element in v will be between 1 and 1,000,000,000, inclusive.
limit will be between 1 and 1,000,000,000, inclusive.

Examples

```
{100,100}
```
```
{2,3}
```
```
{3,5}
```
```
6
```
```
Returns: 10
```
You have two types of items. Items of type 0 have weight 2 and value 3. Items of type 1 have weight 3 and value 5. You have 100 items of each type. The weight limit is 6. The best solution is to take two items of type 1. The total value will be 5 + 5 = 10.
```
{100,100}
```
```
{2,3}
```
```
{3,5}
```
```
5
```
```
Returns: 8
```
We have the same items as in Example 0, but now the weight limit is only 5. In this setting the best solution is to take one item of each type. The total value will be 3 + 5 = 8.
```
{100,102}
```
```
{2,3}
```
```
{3,5}
```
```
1000000000
```
```
Returns: 810
```
Again we have the same 200 items. This time, the weight limit is 10^9 and the optimal solution is to take all 200 items.
```
{100,100}
```
```
{2,3}
```
```
{3,5}
```
```
1
```
```
Returns: 0
```
We can't take anything.

{1,2,3,4,5,6,7,8}

{4,2,6,7,5,8,3,1}

{3,6,4,1,2,8,5,7}

Returns: 73

{1000000000}

{1}

{1000000000}

1000000000

Returns: 1000000000000000000

Note that the answer can be very large.

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.