의도된 시간복잡도
🔒시간 제한
2.000 S메모리 제한
512 MB제출 수
3정답 수
1정답률
50.000%
문제 설명
최대 $S$의 무게를 담을 수 있는 배낭과 $N$개의 물건이 있다. $i$번째 물건은 무게 $w_i$, 가치 $v_i$를 갖는다. 각 물건은 최대 한 번만 담을 수 있으며, 무게 $S$를 넘지 않는 선에서 자유롭게 물건을 담을 수 있다.
이때, 담는 물건들의 가치 합의 최댓값을 구하여라.
입력 설명
첫째 줄에 물건의 개수 $N$과 배낭에 담을 수 있는 최대 무게 $S$가 공백으로 구분되어 주어진다. $(1 ≤ N ≤ 100; 1 ≤ S ≤ 100,000)$
둘째 줄부터 $N$개의 줄에 걸쳐 각 물건의 $w, v$가 공백으로 구분되어 주어진다. $(1 ≤ w, v ≤ 100,000)$
입력으로 주어지는 수는 모두 정수이다.
출력 설명
첫째 줄에 문제의 정답을 출력한다.
예시 1
입력
5 10
1 2
4 4
5 3
3 3
2 1
출력
10힌트
입력으로 주어지는 물건의 순서에서 $1, 2, 4, 5$번째 물건을 담으면 총 $10$의 가치를 낼 수 있으며, 이보다 높은 가치를 내도록 담는 방법은 존재하지 않는다.
기여
만든 사람 : pill27211