배낭채우기2 > 문제은행 : 정보올림피아드&알고리즘



1278 : 배낭채우기2

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
2209 회   
시도횟수
5890 회   

문제

정올 보석상에 도둑이 침입했다. 도둑은 배낭에 보석을 훔치려고 한다. 이때, 훔친 보석의 무게가 W를 넘어가면 배낭이 망가진다.


각 보석의 값어치와 무게가 주어질 때, 도둑은 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되도록 보석을 배낭에 담으려고 한다. 이때 배낭에 담을 수 있는 최대 값어치를 구하시오.


입력형식

입력의 첫 줄은 보석의 개수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 

둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi ( 1 <= Pi < 10,000)가 주어진다. 

단, 보석은 각 종류별로 1개씩이다.


출력형식

출력은 보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되는 최대값을 출력한다.

입력 예

4 14
2 40 
5 110 
10 200 
3 50

출력 예

250

다이나믹

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP