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 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?
The first line will have a single integer , the number of items.
The next lines will each have two integers, and .
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
Sample Input 2
1 1 -9000
Sample Output 2
so what is the capacity of the knapsack...... sorry i am stupid...:-(
This value isn't given in the question, since it's what you're trying to determine.
OHHHHHHH! Get it! Thanks!