...쌕이라고 하면 학생 분들이 매고 다니는 가방 같은것을 말하죠.
...Greedy(욕심쟁이) 알고리즘을 배우신 분들이시라면 다시 한번
...회상에 잠기시는 기회가 되시길 바랍니다.
http://www.koiz.net/algo/greedy-2.htm
Knapsack Problem
안녕하세요?
그리디를 이용하여 배낭(Knapsack)문제를 풀어보려고 합니다.
이 배낭문제는 Dynamic Programming으로 최적해를 100% 보장하는 솔루션이 있긴하지만
그리디 강좌 이므로!! (-_- ;) 그리디를 이용한 배낭문제를 풀어보도록 하겠습니다.
배낭문제는 다 아시죠? 모르시는 분들을 위해 간단히 설명하겠습니다.
------------------------------------------------------------------------------------
배낭에 물건들을 채우려고 하는데, 배낭이 담을 수 있는 무게는 한정되어 있고
각각의 물건들은 자기만의 값어치와 무게를 가진다. 어떻게 하면 배낭이 담을 수
있는 무게를 넘지 않고 최대의 값어치를 얻을 수 있도록 물건들을 배낭에 넣을 수
있을 것인가? (물건은 안쪼개진다)
(Knapsack Problem : 배낭문제)
------------------------------------------------------------------------------------
앞 강좌를 보신분이라면 그리디를 이용한 해법이 딱~ 떠오르실겁니다.
어떤 기준을 정하여 우선순위를 정해 넣는거죠. 여기서 기준이라는 것은 무게가 될 수도
있고 값어치가 될 수 도 있습니다. 그리고 무게는 가장 무거운부터라던가 가장 작은
거부터라던가..
====빰~빠~빠밤!=====> 예제맨~ 예제를 들어서 해보도록 하죠 (음..너무설치는군. )
물건 번호 - 1 2 3 4 5
무게 (weight) 3 4 7 8 9
값어치(value) 4 5 10 11 13
가방의 무게 : 17kg
이렇게 구성 되어 있다면 우린 3가지로 나누어서 생각해 볼수 있습니다.
/* 문제에서는 쪼갬이 불가능 하다고 하였지만 그리디 방법 중 최선의 경우를 모색하기
위하여 물체가 쪼개지는것으로 간주하여 값을 정리합니다. 나중에 문제 풀때에는 아무
상관이 없습니다 */
i ) 가장 무거운거 부터 넣어보면,
5번 과 4번 : 17kg : 24원( 편의상 원으로 하죠... ㅡㅡ )
ii ) 가장 가벼운거 부터 넣어보면,
1번과 2번과 3번 과 4번: 14+3/8*11kg : 23.12원
iii) 가장 값어치 있는거 부터
5번 과 4번 : 17kg : 24원
이렇게 대충 비교해 보면 1번과 3번이 좀 더 높은 값을 가진다는 것을 알 수 있습니다. 그런데
이 데이터에서는 특이하게 값어치와 무게가 양의 상관관계를 가지는군요. 그래서 1번과 3번
방법이 비슷하게 나왔습니다.
우선 기본적으로 이 세가지 방법을 생각 할 수 있고, 또 한가지 생각할 수 있는 것은
무게에 대한 가치를 각각 구해 그중 가장 큰 것부터 고르는 방법이 있습니다.
그렇게 되면,
iv) 1번 : 4/3
2번 : 5/4
3번 : 10/7
4번 : 11/8
5번 : 13/9
이 중 값이 젤 큰 것부터,
5번 + 3번 + 4번 : 17kg : 13 + 10 + 1/8*11 = 24.38원
이 방법이 가장 좋죠? 이렇게 해서 이때까지 네가지의 그리디 방법 중 4번째 것이 가장
좋다고 판정되었습니다. 그러면 이걸 쓰는거죠. 그리디라 해도 너무 욕심쟁이 바보 멍청이
그리디 방법을 쓰면 안되니까 이렇게 조목조목 따져가면서 하는 것입니다.
[출처] [펌] Knapsack Problem |작성자 라이온킹