Connection Status:
Competition Arena > ClassicProblem

ClassicProblem

SRM 674 · 2015-11-03 · by cgy4ever

SRM 674 · 2015-11-03 · by cgy4ever · Dynamic Programming, Greedy
Class Name: ClassicProblem
Return Type: long
Method Name: maximalValue
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

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.

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
0)
{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.

1)
{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.

2)
{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.

3)
{100,100}
{2,3}
{3,5}
1
Returns: 0

We can't take anything.

4)
{1,2,3,4,5,6,7,8}
{4,2,6,7,5,8,3,1}
{3,6,4,1,2,8,5,7}
15
Returns: 73
5)
{1000000000}
{1}
{1000000000}
1000000000
Returns: 1000000000000000000

Note that the answer can be very large.

Submissions are judged against all 168 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ClassicProblem with a public method long long maximalValue(vector<int> cnt, vector<int> w, vector<int> v, int limit) · 168 test cases · 2 s / 256 MB per case

Submitting as anonymous