[DP - 다이나믹 프로그래밍] 냅색문제

대학생 때부터 나를 괴롭혔던 DP..
DP 뿌리를 뽑아버리자!!



아주 전형적인 DP의 대표적인 문제 0 - 1 냅색 문제이다.

문제

물건 A, B, C, D가 있고 각각의 value와 weight가 정의되어 있다.
가방에 최대로 넣을 수 있는 무게제한이 주어질 때 무게제한 안에서 최대한의 value로 물건을 가방에 담는 문제이다

다음과 같이 문제가 주어졌다고 하자.

무식하게 생각해볼까?
그냥 편하게 툭 생각해볼 수 있는 것은 Brute Force 방법이다.

각각의 물건을 담는다(T)와 담지 않는다(F)로 나뉠 수 있고 time complexity는 2^n 이다.
우리는 이것보다는 더 효율적으로 답을 구해내야만 한다..!


DP를 적용할 수 있는 문제인지 여부는 다음을 판단해보면 된다.

• 더 작은 문제(sub problem)로 쪼개질 수 있다.
• sub problem으로 상위 문제의 솔루션을 구할 수 있다.
• sub problem 끼리 겹치는 부분이 있다. => Memoization을 통해 필요한 계산 수를 크게 줄일 수 있다.

A, B, C, D중에 무게제한 5이내에서 밸류가 최대가 되게끔 고르는 문제 이므로
이 문제는 D를 골랐을 때와 고르지 않았을 때로 쪼개볼 수 있다. 각각의 상황에서 현재의 무게와 밸류를 계산해가면서 문제를 계속 쪼갤 수 있다.

NS(Nap Sack의 줄임)함수를 최대 밸류를 리턴하는 함수라 하고,
NS(현재 고를 수 있는 물건들, 현재 무게 제한)으로 정의한다면 다음 트리와 같이 최종적으로 구해야 할 문제를 더 작은 문제들로 쪼개 볼 수 있다.

이를 점화식을 이용해서 나타내면, 아래와 같다.
n은 몇 번 물건까지 있는지를 나타낸 것이고
w는 현재 상태에서 무게의 limit이다.

NS(n,w)함수는 n과 w 2개를 인자로 받고 있으니 다음처럼 2차원 배열로 나타낼 수 있다.
2차원 배열에서 행 기준 가로로 쭈욱 채워보았다.

시간복잡도는 n * w이고 공간복잡도도 n * w이다.
그런데 NS 함수를 계산하기 위해서는 n-1 행만 있으면 계산이 가능하므로 공간복잡도는 n이라고도 볼 수 있다.

점화식을 바탕으로 작성한 수도코드이다.

이렇게 한 번 쭈욱 살펴보니 그렇게 어렵지만은 않은 것 같다.
DP문제도 꾸준히 연습만 하면 익숙해 질 수 있을 것 같다🥶
다시보니 글씨가 매우 악필이다ㅠㅠㅠ,,다음엔 더 예쁘게써야지