[주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

게티이미지뱅크 제공

여행을 떠나기 전 짐을 싸는 건 여간 귀찮은 일이 아니다. 생각나는 대로 짐을 챙기다 보면 짐이 가방에 다 들어가지 않아 난감할 때도 있다. 그런데 수많은 짐 중 어떤 것부터 골라서 싸야 하는지 알려주는 수학 이론이 있다. 바로 '배낭 문제'다.

배낭 문제란 넣을 수 있는 물건의 총량이 제한된 배낭에 가치의 합이 최대가 되도록 물건을 담는 조합 최적화 문제다. 이때 선택한 물건들의 무게 합은 주어진 최대 무게를 초과하면 안 된다. 배낭 문제는 단순해보이지만, 모든 경우의 수를 직접 확인해봐야 해서 답을 구하기가 어렵다.

최대 용량이 10kg인 배낭에 다음과 같은 짐을 담는 상황을 생각해보자. 배낭 문제를 통해 배낭에 담는 물건의 합이 10kg 이하가 되면서 물건 가치의 합은 최대가 되는 경우를 찾을 수 있다. 여기에는 무게순, 가치순, 무게당 가치순으로 배낭을 꾸리는 세 가지 방법이 있다.

(왼쪽 방법1부터)무게가 무거운 짐부터 배낭을 꾸리면 배낭에는 쌀, 여벌 옷, 음료수, 손전등을 담을 수 있다. 이때 가치의 합은 18점이다, 가치가 높은 것부터 배낭을 꾸리면 배낭에는 구급약, 음료수, 쌀, 손전등까지 담을 수 있다. 이때 가치의 합은 19점이다, 무게당 가치가 높은 것부터 배낭을 꾸리면 배낭에는 쌀을 제외하고 모두 담을 수 있다. 이때 가치의 합은 24점이다. 수학동아 제공

위의 세 가지 방법 중 '방법 3'으로 배낭을 꾸릴 때 가치의 합이 최대가 된다. 하지만 이 방법 역시 모든 물건을 넣을 수는 없다. 이는 우리가 '0-1 배낭 문제' 를 풀었기 때문이다. 0-1 배낭 문제는 짐을 넣거나 빼거나 둘 중 하나만 선택하는 문제다.

모든 짐을 조금씩 가져가고 싶다면 짐을 쪼개서 가져갈 수 있는 '분할 가능 배낭 문제'를 이용하면 된다. 0-1 배낭 문제는 이를 풀기 위한 가장 효과적인알고리듬이 알려져 있지 않아 여러 조합을 탐색해봐야 하는 반면 분할 가능 배낭 문제는 그리디 알고리즘(여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 근사적으로 최적의 해를 구하는 데 쓰이는 방법)으로 해결할 수 있다.

※관련기사
수학동아 6월, 설레는 여행지에서 효율적으로 짐 싸기 배낭 문제

[수학동아 편집부 ]