DMOPC '17 Contest 2 P1 - 0-1 Knapsack

View as PDF
Submit solution
Points: 3
Time limit: 4.0s
Memory limit: 64M
Author:
Kirito
Problem type

A classical problem in Computer Science is the 0-1 Knapsack problem. In this problem, you are given N items with the ith item takes up a capacity of c_i and has a value of v_i, and a knapsack with capacity C, and try to maximize the sum of the value of the items in the knapsack while not exceeding the capacity of the knapsack.

Unfortunately, your knapsack has just broke (again). Since you can't fix it, you decide to get a new knapsack. Upon doing so, you shall attempt to solve the knapsack problem with this new knapsack. What size of knapsack will maximize the value of the items you can get?

Constraints

1 \le N \le 10^5
-10^9 \le v_i \le 10^9
0 \le c_i \le 10^5

Input Specification

The first line will have a single integer N, the number of items.
The next N lines will each have two integers, c_i and v_i.

Output Specification

A single non-negative integer, the minimum size of the knapsack that maximizes the sum of the values of the item you place in your knapsack.

Sample Input 1

2
1 0
9 2

Sample Output 1

9

Sample Input 2

1
1 -9000

Sample Output 2

0

Comments


  • 3
    IanHu  commented on Nov. 11, 2018, 5:18 a.m.

    so what is the capacity of the knapsack...... sorry i am stupid...:-(


    • 0
      Kirito  commented on Nov. 11, 2018, 7:23 a.m.

      This value isn't given in the question, since it's what you're trying to determine.


      • 1
        IanHu  commented on Nov. 12, 2018, 12:13 a.m.

        OHHHHHHH! Get it! Thanks!