Clink 문제 바로 가기 : JUNGOL
문제 : 배낭채우기 (1077)
제한시간 |
1 Sec |
메모리제한 |
64 mb |
|
|
입력 형식 :
첫 줄은 보석의 가지 수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다.
둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi가 주어진다. (단, 각각의 보석의 개수는 무제한으로 가정한다.)
출력 형식 :
보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서, 보석의 총 값어치가 최대가 되는 최대값을 출력한다.
입력 예 |
|
출력 예 |
4 14 |
|
300 |
2 40 |
|
|
5 110 |
|
|
3 50 |
|
|
|
|
|
참고 이론 : 배낭문제 (출처 : 위키피디아)
배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다. 이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 의사 다항 시간에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 오스카 이바라와 김철언이 1975년에 개발하였다.[1] |
개인적 풀이 :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| 1 | 0 | 0 | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 2 | 0 | 0 | 40 | - | - | - | - | - | - | - | - | - | - | - | - |
| 3 | 0 | 0 | 40 | 50 | - | - | - | - | - | - | - | - | - | - | - |
| 4 | 0 | 0 | 40 | 50 | 80 | - | - | - | - | - | - | - | - | - | - |
| 5 | 0 | 0 | 40 | 50 | 80 | 110 | - | - | - | - | - | - | - | - | - |
| 6 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | - | - | - | - | - | - | - | - |
| 7 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | - | - | - | - | - | - | - |
| 8 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | - | - | - | - | - | - |
| 9 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | - | - | - | - | - |
| 10 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | 220 | - | - | - | - |
| 11 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | 220 | 230 | - | - | - |
| 12 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | 220 | 230 | 260 | - | - |
| 13 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | 220 | 230 | 260 | 270 | - |
| 14 | 0 | 0 | 40 | 50 | 80 | 110 | 120 | 150 | 160 | 190 | 220 | 230 | 260 | 270 | 300 |
전략 : DP 에서는 일정한 패턴의 값은 미리 Table 화 하여 값을 가지고 있는다.
위의 Table 에서 보듯이 1 -> 2 -> 3 -> 4 -> 5 ... 순으로 마지막 14까지 값을 구한다.
노란색 부분은 값의 최대(노란 색 부분이 꼭 구해진 값이라는 보장은 없다) 값으로 설정된 구간을 말함
최종 무게가 14 를 가지기 위한 최대 값은 "300" 이다.