여행 가방
골드 V의견: 0
여행을 떠나는 준서는 짐을 챙기려 한다. 챙길 수 있는 물건은 \(N\)개이고, 각 물건 \(i\)에는 무게 \(w_i\)와 가치 \(v_i\)가 있다.
준서의 가방은 무게의 합이 \(W\) 이하인 물건들만 담을 수 있다. 가방에 담은 물건들의 가치 합이 최대가 되도록 하려고 한다.
가방에 담을 수 있는 물건들의 가치 합의 최댓값을 구하시오. 각 물건은 담거나 담지 않거나 둘 중 하나이며, 같은 물건을 두 번 담을 수는 없다.
- \(1 \le N \le 100\)
- \(1 \le W \le 100\,000\)
- 각 물건의 무게 \(w\)는 \(1\) 이상 \(100\,000\) 이하의 정수이다.
- 각 물건의 가치 \(v\)는 \(1\) 이상 \(1\,000\) 이하의 정수이다.
첫째 줄에 물건의 수 \(N\)과 가방이 버틸 수 있는 무게 \(W\)가 주어진다.
다음 \(N\)개의 줄에 각 물건의 무게 \(w\)와 가치 \(v\)가 공백으로 구분되어 주어진다.
가방에 담을 수 있는 물건들의 가치 합의 최댓값을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(1 \le N \le 20\) |
Subtask 2 | 60점 | 추가 제한이 없다. |
4 7
6 13
4 8
3 6
5 1214무게 \(4\)(가치 \(8\))와 무게 \(3\)(가치 \(6\))인 물건을 담으면 무게 합이 \(7\)로 한도를 넘지 않고, 가치 합은 \(8 + 6 = 14\)로 최대이다.
3 10
5 10
4 40
6 3070무게 \(4\)(가치 \(40\))와 무게 \(6\)(가치 \(30\))을 담으면 무게 합 \(10\), 가치 합 \(40 + 30 = 70\)으로 최대이다.
rip 작성
출처 지정되지 않음
평가 및 의견
여행 가방
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
여행 가방