[알고리즘] 배낭 문제 (Knapsack Problem)

🎒배낭문제 (Knapsack Problem)

배낭문제는 조합 최적화 문제의 일종이다.

 

간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분 집합을 찾는 문제이다.

 

분할 가능한 배낭 문제	0-1 배낭 문제

 

배낭 문제는 분할 가능한 배낭 문제와, 0-1 배낭 문제로 나뉘어 진다.

위 그림을 통해 보면, A박스를 열어 12kg의 금괴 중 일부만을 챙겨 갈 수 있는 문제가 '분할 가능한 배낭 문제'이고, 

박스를 열지 못해 금괴 일부를 꺼내지 못하고 통째로만 취급하는 문제가 '0-1 배낭 문제'이다.

 

분할 가능한 배낭 문제는 그리디 알고리즘으로 풀 수 있다.

반면, 0-1 배낭 문제는 그리디 알고리즘으로 최적해를 찾을 수 없어 동적 계획법이나 백트래킹 같은 조합 최적화 문제의 풀이 방법을 이용해야 한다.