여행 가방 채우기
실버 III의견: 0
탐험가 하진이는 여행을 떠나기 전에 배낭에 물건을 담으려 한다. 물건은 총 \(N\)가지이며 \(i\)번 물건의 무게는 \(w_i\) 그램, 가치는 \(v_i\) 원이다.
배낭의 최대 적재량은 \(W\) 그램이다. 각 물건은 얼마든지 잘라서 담을 수 있다. 즉, \(i\)번 물건의 \(0\) 이상 \(w_i\) 이하 임의의 실수 그램만큼 담을 수 있으며, 이때 얻는 가치는 무게에 비례한다.
배낭에 담을 수 있는 물건의 최대 가치를 소수점 셋째 자리까지 출력하여라.
- \(1 \le N \le 100\,000\)
- \(1 \le W \le 10^{12}\)
- \(1 \le w_i \le 10^6\)
- \(1 \le v_i \le 10^9\)
첫째 줄에 물건의 수 \(N\)과 배낭 용량 \(W\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 각 물건의 무게 \(w_i\)와 가치 \(v_i\)가 공백으로 구분되어 주어진다.
배낭에 담을 수 있는 물건의 최대 가치를 소수점 셋째 자리까지 출력한다.
예를 들어 최대 가치가 정확히 \(24.5\)원이라면 \(24.500\)으로 출력한다.
3 8
4 10
3 12
6 15
24.500
단위 무게당 가치는 각각 \(2.5\), \(4.0\), \(2.5\)원이다. 가치 밀도가 가장 높은 \((3, 12)\)를 먼저 전부 담으면 \((3\text{g}, 12\text{원})\)이 채워져 남은 용량은 \(5\text{g}\)이다. 다음으로 \((4, 10)\) 또는 \((6, 15)\) 중 밀도가 같은데 \((4, 10)\)을 전부 담으면 \(16\text{g}\)에서 용량 초과이므로 \((4, 10)\)을 전부 담고(\(+10\)원) 남은 \(1\text{g}\)에 \((6, 15)\)의 \(\frac{1}{6}\)을 담아 \(+2.5\)원을 추가한다. 합계 \(12 + 10 + 2.500 = 24.500\)원이다.
3 5
2 6
2 6
2 6
15.000
세 물건 모두 단위 무게당 가치가 \(3\)원으로 같다. 물건 두 개를 전부 담으면 \(4\text{g}\)에 \(12\)원, 나머지 \(1\text{g}\)에 세 번째 물건의 절반을 담으면 \(+3\)원이 추가되어 합계 \(15.000\)원이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
여행 가방 채우기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
여행 가방 채우기