Informatica Online Judge

  0/1 배낭문제 (Tiny) [2157 / 086D]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 9   Total Tried : 8


The Champion of this Problem (C++) : gs17106 - 0ms / 140byte
My Best Submission (C++) : N/A

[codeup.kr]

Background

어떤 배낭에 W무게 만큼 물건을 담을 수 있다.

물건들은 (무게 Wi, 가격 Vi) 정보를 가지고 있는데, 물건들을 조합해서 담아 가격의 총합이 최대가 되게 하려고 한다.

물건들은 한 종류씩 밖에 없으며, 절대 배낭의 무게를 초과해서는 안 된다.

Input

첫째 줄에 물건의 개수 N(1<= N <= 20)과 배낭의 무게 W( 1 <= W <= 10000 )가 입력된다.

둘째 줄부터 N+1째줄 까지 물건들의 정보가 wi, vi가 한 줄에 하나씩 입력된다. ( 1 <= Wi, Vi <= 100 )

Output

배낭의 무게 W를 초과하지 않으면서 물건의 가격의 총합의 최대값을 출력한다.

IO Example

입력
4 5
2 3
1 2
3 3
2 2

출력
7
* 설명

1, 2, 4번 물건을 고른 결과이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]