Knapsack Problem
Knapsack algorithm : 전북대 박순철 교수님 동영상 (★★★)
우리 가족은 1년간의 긴 여행을 떠나기 위하여 준비하기 시작했다. 1년간의 여행을 떠나기 위한 준비는 가서 머물 집과 입국에 대한 서류 그리고 가져갈 짐을 꾸리는 일이었다. ..... 원하는 물건을 다 가져 갈 수 없으니 선택 기준이 필요했다. 지영이가 가방에 먼저 넣은 물건은 목욕용 어린이 샴푸와 바디로션 그리고 핑클의 노래가 담긴 카세트 테이프였다. 자기는 제일 맘에 드는 것을 가지고 가고 싶어 선택했다고 한다. 지민이의 선택 기준은 달랐다. 우선 부피가 적으면서도 지영이와 마찬가지로 자기가 가장 아끼는 것, 게임 CD와 약간의 책이었다. 필요하면서도 부피가 작은 것이 지민이의 선택 기준이었다. 어른들의 선택 기준은 여기에 한가지 더 추가된다. 필요하고 부피가 작은 것이면서 한국에서 가져가는 비용이 미국에서 새로 사는 비용보다 적을 것…. 그러니까 가져갈 물건들에 대한 그곳에서의 필요성과 가치 판단이 필요했다. ....
배낭문제 (Knapsack problem) 은 가방과 같이 한정된 부피 내에서 최대 비용 효과를 얻는 물건의 선택 조합을 구하는 문제이다. 우리가 살아가면서 참 많은 Knapsack problem 을 만나게 된다. 받은 월급으로 어떤 곳에 써야 할지, 어떤 일에 한정된 노력을 투자할 것인지, 제한된 시간에 누구를 만나야 할지, 이런 것들이 모두 Knapsack 문제이다. ..... (최은만 2000)