우주 탐험 장비
골드 I의견: 0
우주 비행사 레아는 탐험 임무를 위해 \(N\)개의 장비 중 일부를 골라 우주선에 실으려 한다. 우주선에는 질량 한도 \(M\)과 부피 한도 \(V\)가 있다. 선택한 장비들의 질량 합이 \(M\) 이하이고 부피 합이 \(V\) 이하여야 한다. 각 장비는 최대 한 번 선택할 수 있다.
장비 가치 합의 최댓값을 구하여라.
- \(1 \le N \le 100\)
- \(0 \le M, V \le 1\,000\)
- \(1 \le m_i \le M\) (단, \(M > 0\)일 때)
- \(1 \le v_i \le V\) (단, \(V > 0\)일 때)
- \(1 \le p_i \le 1\,000\)
첫째 줄에 장비의 수 \(N\), 질량 한도 \(M\), 부피 한도 \(V\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 장비 \(i\)의 질량 \(m_i\), 부피 \(v_i\), 가치 \(p_i\)가 공백으로 구분되어 주어진다.
선택할 수 있는 장비 가치 합의 최댓값을 출력한다.
4 7 6
4 3 12
2 5 10
3 2 8
5 4 15
20
질량 한도 \(7\), 부피 한도 \(6\). 장비 \(1\)(질량 \(4\), 부피 \(3\), 가치 \(12\))과 장비 \(3\)(질량 \(3\), 부피 \(2\), 가치 \(8\))을 선택하면 질량 \(7\), 부피 \(5\), 가치 \(20\)이다. 장비 \(1\)과 \(4\)는 질량 \(9 > 7\)이라 불가. 최선: \(20\).
3 5 5
10 1 100
1 10 100
3 3 50
50
장비 \(1\)은 질량 초과, 장비 \(2\)는 부피 초과. 장비 \(3\)만 두 조건을 모두 만족하여 가치 \(50\)이다.
riseoj 작성
출처 Original
평가 및 의견
우주 탐험 장비
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
우주 탐험 장비