[알고리즘] knap-sack(냅색, 0-1 배낭문제)

안녕하세요? 코딩충입니다.

오늘은 코딩계에서 꽤나 유명한 knap-sack 문제에 대해서 포스팅 하겠습니다.

사람들에 따라서 베낭 문제, 보석가게 도둑 문제 등등 다양한 이름으로 불리웁니다.

문제에 나오는 사람도 도둑, 여행자 등 다양하고 

가방, 배낭 등 들고가는 것도 다양하며,

가지고 가는 것도 보석, 짐 등 다양하며, 

한정된 것도 무게, 크기 등 다양하며, 

짐을 나눌 수 있는 문제와 없는 문제 등 다양합니다.

하지만 핵심은 같습니다.

자원을 희생시켜서 이득을 얻을 때 최소 자원으로 최대 이득 얻기.

저희는 이 다양한 문제들 중에서 0-1 베낭 문제를 다루겠습니다.

가장 간단하고 기본적인 문제입니다.

0-1 배낭문제와 다른 변형문제들은 이 포스팅의 메인 주제가 아니니, 

위키피디아를 참고해주시길 바랍니다.

0-1 배낭문제가 뭔지 아시려면 꼭 읽어보셔야 됩니다.

이제 이해가 되셨으리라고 믿고 본론으로 들어가겠습니다.

먼저 DP문제이기 때문에 DP포스팅에서 얘기한 "가이드 라인^[각주:1]"을 따르겠습니다.

1. 2차원 DP로 하겠습니다.

2. i = 남은 무게, j = 현재 쳐다보는^[각주:2] 보석의 번호(인덱스, index)

3. 물론 최대의 이득이죠

4. 단순하게 생각했을때 현재 쳐다보는 보석을 가방에 넣든지 안 넣든지 두 가지 경우 밖에 없는데 그 두가지 경우의 최대값이겠죠?

점화식은

D[i][j] = max(D[i][j + 1], D[i - w[j]][j + 1] + v[j])

입니다. 

즉 이번 보석을 그냥 넘기고 다음 보석 j + 1으로 넘기는 경우의 수와

이번 보석을 사기 때문에 남은 무게가 w[j] 즉 j번째 보석의 무게만큼 줄어들고 그 대신 v[j] j번째 보석의 가치만큼 늘어나는 경우의 수

둘의 최댓값이겠죠?

Dp 테이블^[각주:3]을 채워봐도 알아낼 수 있습니다.

5. 4의 점화식을 이용하여 재귀 또는 for문 DP로 계산합니다.

CONTENT BY 코딩충

1. ※ 동적 계획법(DP) 문제 해결 방법(가이드 라인) 1. 몇 차원(=변수 개수) DP를 할 것인가? 2. 변수 개수(=차원)가 정해졌으면 각각의 변수가 무슨 의미인가? 3. DP값이 어떤 의미인가? 4. 어떤 DP값과 다른 DP값의 관계가 있는가? 있으면 어떤 관계인가? --> 4을 알아내기 위해서 DP 테이블을 직접 채워보시면 가장 확실하게 알 수 있습니다 5. 4의 점화식을 이용하여 재귀 또는 for문 DP로 계산한다. [본문으로]
2. 정확한 표현은 아니지만 대략적으로 비슷한 의미이다. [본문으로]
3. DP값의 표인데 테이블이라고 부른다. 즉 DP이차원 배열이라고 생각하면 된다. [본문으로]