E - Knapsack 2

Contest Duration: 2019-01-06(Sun) 11:00 - 2019-01-06(Sun) 16:00 (local time) (300 minutes)

E - Knapsack 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $100$ 点

問題文

$N$ 個の品物があります。品物には $1, 2, \ldots, N$ と番号が振られています。各 $i$ ( $1 \leq i \leq N$ ) について、品物 $i$ の重さは $w_i$ で、価値は $v_i$ です。

太郎君は、 $N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量は $W$ であり、持ち帰る品物の重さの総和は $W$ 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

入力はすべて整数である。
$1 \leq N \leq 100$
$1 \leq W \leq 10^9$
$1 \leq w_i \leq W$
$1 \leq v_i \leq 10^3$

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $W$ 
 $w_1$   $v_1$ 
 $w_2$   $v_2$ 
 $:$ 
 $w_N$   $v_N$

出力

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

品物 $1, 3$ を選べばよいです。すると、重さの総和は $3 + 5 = 8$ となり、価値の総和は $30 + 60 = 90$ となります。

入力例 2Copy

Copy

1 1000000000
1000000000 10

出力例 2Copy

Copy

入力例 3Copy

Copy

出力例 3Copy

Copy

品物 $2, 4, 5$ を選べばよいです。すると、重さの総和は $5 + 6 + 3 = 14$ となり、価値の総和は $6 + 6 + 5 = 17$ となります。

Score : $100$ points

Problem Statement

There are $N$ items, numbered $1, 2, \ldots, N$ . For each $i$ ( $1 \leq i \leq N$ ), Item $i$ has a weight of $w_i$ and a value of $v_i$ .

Taro has decided to choose some of the $N$ items and carry them home in a knapsack. The capacity of the knapsack is $W$ , which means that the sum of the weights of items taken must be at most $W$ .

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.
$1 \leq N \leq 100$
$1 \leq W \leq 10^9$
$1 \leq w_i \leq W$
$1 \leq v_i \leq 10^3$

Input

Input is given from Standard Input in the following format:

 $N$   $W$ 
 $w_1$   $v_1$ 
 $w_2$   $v_2$ 
 $:$ 
 $w_N$   $v_N$

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Items $1$ and $3$ should be taken. Then, the sum of the weights is $3 + 5 = 8$ , and the sum of the values is $30 + 60 = 90$ .

Sample Input 2Copy

Copy

1 1000000000
1000000000 10

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

Items $2, 4$ and $5$ should be taken. Then, the sum of the weights is $5 + 6 + 3 = 14$ , and the sum of the values is $6 + 6 + 5 = 17$ .