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" 이다. 





+ Recent posts