## DMOPC '17 Contest 2 P1 - 0-1 Knapsack

View as PDF

Points: 3
Time limit: 4.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A classical problem in Computer Science is the 0-1 Knapsack problem. In this problem, you are given items with the th item takes up a capacity of and has a value of , and a knapsack with capacity , and try to maximize 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?

#### Input Specification

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

#### 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

• commented on March 7, 2019, 9:45 p.m.

Where is the input for the maximum capacity of the knapsack?

• commented on Nov. 11, 2018, 12:18 a.m.

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

• commented on Nov. 11, 2018, 2:23 a.m.

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

• commented on Nov. 11, 2018, 7:13 p.m.

OHHHHHHH! Get it! Thanks!