8577: DPL_1_F : 0-1 Knapsack Problem II
[Creator : ]
Description
You have $N$ items that you want to put them into a knapsack. Item $i$ has value vi and weight $w_i$.
You want to find a subset of items to put such that:
- The total value of the items is as large as possible.
- The items have combined weight at most $W$, that is capacity of the knapsack.
Find the maximum total value of items in the knapsack.
Input
The first line consists of the integers N and W.
In the following N lines, the value and weight of the $i$-th item $v_i\ w_i$ are given.
Output
Print the maximum total values of the items in a line.
Constraints
$1 ≤ N ≤ 100$
$1 ≤ vi ≤ 100$
$1 ≤ w_i ≤ 10,000,000$
$1 ≤ W ≤ 1,000,000,000$
$1 ≤ vi ≤ 100$
$1 ≤ w_i ≤ 10,000,000$
$1 ≤ W ≤ 1,000,000,000$
Sample 1 Input
4 5
4 2
5 2
2 1
8 3
Sample 1 Output
13
Sample 2 Input
2 20
5 9
4 10
Sample 2 Output
9