58. 배낭 문제 (knapsack problem) - 도둑의 고민

-개요-

배낭 문제는, knapsack problem이라 불리는 유명한 조합 최적화 분야의 문제로 불린다고 한다.

NP-난해에 속하는 문제로, 여기서 NP란 복잡도의 일종으로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다.

여기서 다항 시간이란 Polynomial Time을 말한다. 

즉, 빅 오 표기법으로 O(n^c) n제곱, n의 세 제곱, ... , n의 c제곱을 일컫는다.

지수적 시간인 Exponential Time과는 다르다. 지수적 시간은 O(c^n)을 일컫는다. 2^n, 3^n ...

이 문제의 대표적인 문제인 '도둑과 고민' 문제다.

알고리즘은 57챕터인 모든 부분집합을 출력하는 방식을 활용하여 그 토대로 작성되었다.

-문제-

'한 도둑이 주거집을 침입했다. 이 때, 도둑 눈 앞으로는 여러가지 가치있는 물건들이 존재한다. 찾아낸 물건은 총 N개였다.

이 때, 도둑은 자신이 이 모든 물건을 가져갈 수 없다는 것을 알았다. 왜냐하면 자신이 가져온 배낭이 모든 물건을 담을 수

없기 때문이다. 이 상황에서 도둑이 가장 효율적으로 물건을 훔칠 수 있는 방법은 무엇인가.'

'가장 효율적으로 훔친 물건들의 가치 합과 각 물건들을 출력하시오.'

이 문제의 풀이는 단순하다.

도둑이 가져갈 수 있는 모든 물건들의 조합을 찾고, 그 중에서 자신의 가방에 담을 수 조합만 추린다.

그리고 그 조합중에서 물건들의 가치 합이 가장 높은 조합을 찾아낸다.

그렇기에 앞선 57 문제의 모든 부분집합을 찾고, 그 부분집합을 찾을 때마다 처리 알고리즘에 넣으면 된다.

-점화식-

V(capacity, n) = max( value<n-1> + V(capcity-weight<n-1>, n-1), V(capacity, n-1) )

똑같이 현재 물건들을 선택하는 것과, 선택하지 않는 두 분기로 나뉜다.

두 개의 재귀 흐름으로 나뉘기에 수행시간은 O(2^n)이 되야하지만, capacity의 한계가 존재하기 때문에 선형시간에 풀린다.

-코드-

 

-출력-

-정리-

이 문제를 풀면서, 재귀적으로 움직이면서 최종 결과 셋을 출력할 수 있는 새로운 방법을 알아내었다.

획기적인 방식이다. 결국은 전수조사법이지만 부분집합을 모두 구하고 이 부분집합을 계산 함수에 넣어서 풀어내는 방식이

항상 궁금했는데, 이런식으로 재귀 흐름에 Recover 동작없이 풀어내느 것을 알았다.

한 단계 조금 정진한 느낌이다.

결국은 계속 반복된 알고리즘이긴 하지만, 한 번 본 것은 안 본 것이라는 강성태님의 말처럼 계속 새롭다.

조금씩, 조금씩 말과 조건이 변한 것 뿐인데 알고리즘의 축이 변한다.

또한 이 문제를 풀면서 배우게 된 부분이 있다.

바로 재귀 운행의 구조는 결국은 트리 구조다.

2개 분기로 나뉘면 이진 트리, 3개 분기로 나뉘면 노드가 3개 가진 삼항 트리 ... 

머리속으로 드디어 재귀의 구조가 들어온다.

이것을 이제 알다니 바보다. 확실히 독학으로 하면 정말 아주 간단하고 쉬운것인데도 그 본질을 모르고 겉돈다.

다행히 이제라도 알아서 다행이다. 하지만 비록 본질은 느리게 알았지만 이것을 알아가는 과정속에서 그 깊이가

훨씬 깊어지는 것을 느낀다.

그리고 또한 이런 재귀 흐름의 구조에서 결국 재귀의 흐름은 중위 순행이란 것을 알았다.

진짜 이것을 어떻게 이제 깨닫지. 이러니 머릿속에 재귀가 쉽게 쉽게 안들어오지.

너무 선형 구조로만 알고리즘을 생각하는 것 같다. 조금 더 트리나 그래프 구조에 친숙해지자.

이 문제를 풀어내는데 너무 오랜 시간을 사용하였다.

집중이 많이 풀렸다.

진짜 정말 사소한 부분인데, 계속 오류를 못 찾아내고 빙빙 돌다보면 어느새 집중력이 사라진다.

계속 허리피고 공부하자.