마법 아이템 배낭
골드 V의견: 0
마법사 이안은 던전 탐험에서 \(N\)개의 마법 아이템을 발견했다. 각 아이템은 무게 \(w_i\)와 가치 \(v_i\)를 가지며, 이안의 배낭은 무게 합이 \(W\) 이하인 아이템들만 담을 수 있다. 아이템은 같은 것을 두 번 담을 수 없다.
배낭에 담을 수 있는 아이템 가치 합의 최댓값을 구하여라.
- \(1 \le N \le 100\)
- \(1 \le W \le 10\,000\)
- \(1 \le w_i \le W\)
- \(1 \le v_i \le 1\,000\)
첫째 줄에 아이템의 수 \(N\)과 배낭의 무게 한도 \(W\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 각 아이템의 무게 \(w_i\)와 가치 \(v_i\)가 공백으로 구분되어 주어진다.
배낭에 담을 수 있는 아이템 가치 합의 최댓값을 출력한다.
4 7
3 9
4 10
5 16
7 18
19
가방 무게 한도 \(7\)에서 아이템 \(1\)(무게 \(3\), 가치 \(9\))과 아이템 \(2\)(무게 \(4\), 가치 \(10\))를 선택하면 합계 무게 \(7\), 가치 \(19\)로 최대가 된다.
3 5
10 100
6 50
4 30
30
무게 \(6\) 이상인 아이템들은 한도 \(5\)를 초과하므로 담을 수 없다. 무게 \(4\)인 아이템만 선택하면 가치 \(30\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 아이템 배낭
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 아이템 배낭