보물
면접 대비시간 제한1초메모리 제한1024 MB
물건마다 가치와 무게가 있고 가방의 용량이 주어질 때, 한 번에 가져갈 수 있는 물건의 최대 가치 합을 구합니다. 데이터 세트가 여러 개 주어집니다.
문제
해변에서 땅을 파다가 오래된 보물 상자를 발견했다! 상자 안에는 값비싼 희귀 유물이 가득 들어 있다! 안타깝게도 밀물이 보물 상자를 쓸어가기 전에 배까지 가져갈 수 있는 양에는 한계가 있다. 여러 물건의 무게와 가치, 그리고 운반 용량이 주어질 때, 한 번의 이동으로 가져갈 수 있는 물건 가치의 총합이 최대가 되는 값을 구하는 프로그램을 작성하라.
입력
첫 줄에는 데이터 셋의 개수를 나타내는 정수 n이 하나 주어진다. 각 데이터 셋은 물건의 개수 i와 운반 용량 w를 나타내는 두 정수로 시작한다. 이어지는 i개의 줄에는 각각 물건의 가치와 무게를 나타내는 두 수가 주어진다.
출력
각 데이터 셋마다 한 번의 이동으로 가져갈 수 있는 물건 가치의 최댓값을 출력한다.