여행 준비
골드 III의견: 0
알파카는 친구들과 함께 여행을 떠나려고 한다.
여행을 위해 여러 물건을 챙기고 싶지만, 가져갈 수 있는 가방은 단 두 개뿐이다.
두 가방은 각각 최대 C만큼의 무게만 담을 수 있다.
알파카는 총 N개의 물건을 가지고 있으며, 각 물건은 무게와 만족도를 가진다.
각 물건은 최대 한 번만 사용할 수 있으며, 하나의 물건을 여러 가방에 나누어 담을 수 없다.
두 가방의 무게 제한을 넘지 않도록 물건들을 담으며 얻을 수 있는 만족도의 최댓값을
찾아주자.
\(1 ≤ N ≤ 100\)
\(1 ≤ C ≤ 1000\)
\(1 ≤ W ≤ C\)
\(1 ≤ V ≤ 100\,000\)
첫째 줄에 물건의 개수 N과 가방의 최대 용량 C가 주어진다.
이후 N개의 줄에 각 물건의 무게 W와 만족도 V가 주어진다.
두 가방에 담을 수 있는 물건들의 만족도의 최댓값을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(N ≤ 20\) |
2 | 15점 | 모든 물건의 무게는 1 이다. |
3 | 25점 | \(N ≤ 100\), \(C ≤ 300\) |
4 | 50점 | 추가 제한 없음 |
5 5
2 10
3 20
4 25
5 35
1 565첫 번째 가방에 1번,2번 물건을 담고, 두 번째 가방에 4번,5번 물건을 담으면 총 만족도는 70이 된다.
4 4
4 100
4 90
2 30
2 201907 50
50 1000
49 999
1 1
2 2
3 3
4 4
5 520004 10
6 60
4 40
7 70
3 30200한 가방에 7,3 무게의 물건(만족도 70+30=100), 다른 가방에 6,4 무게의 물건(만족도 60+40=100)을 담으면 두 가방 모두 용량 10을 꽉 채우고 최대 만족도 200을 얻는다.
escho0107 작성
출처 지정되지 않음
평가 및 의견
여행 준비
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
여행 준비