물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)

0/1 Knapsack Problem

다이나믹 프로그래밍(Dynamic Programming : DP)을 활용하여 해결할 수 있다..
DP는 큰 문제를 작은 문제로 쪼개서 해결한다.
DP는 Devide-and-Conquer라는 원리에 기반을 두고 있으며, 이전에 계산해둔 값을 메모리(배열 등)에 저장해서 반복 작업을 줄이는 기법(Memoization)이 핵심이다.

가방에 담을 수 있는 물건의 무게와 가치가 아래의 표와 같이 있다고 가정하자.

① 2차원 배열을 만드는데, 이 때, (i + 1)(j + 1) 크기의 배열을 만들고 0으로 초기화한다.

이 때, 행 i는 물건 i(0 ~ 4)까지 넣을 수 있을 때를 의미하고, 열 j(0 ~ 7)는 가방의 최대 무게를 의미한다.

② 첫 번째 물건(무게 = 6, 가치 = 13)을 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 가치를 구한다.

③ 두 번째 물건(무게 = 4, 가치 = 8)을 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 가치를 구한다.

④ 세 번째 물건(무게 = 3, 가치 = 6)을 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 가치를 구한다.

i = 3, j = 7일 때를 보게 되면, DP를 사용하는 이유를 알 수 있다.
가방의 최대 무게가 7일 때, 세번째 물건을 넣고 나서도 가방의 무게가 4가 남게 된다.
따라서, 가방에는 최대 무게가 4일 때와 같은 최대 가치를 더 남길 수 있다.
이때, i = 2, j = 7일때의 값 13과 (i = 3, j = 3일 때의 값) + (i = 2, j = 4일 때의 값)인 14와 비교하여 더 큰 값이 최대 가치로 설정된다.

⑤ 네 번째 물건(무게 = 5, 가치 = 12)을 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 가치를 구한다.

13번째 줄 : N은 물건의 갯수를 의미한다.
14번째 줄 : K는 가방에 들어갈 수 있는 최대 무게를 의미한다.
20번째 줄 : dp는 (N + 1) * (K + 1) 크기의 2차원 배열이 모두 0으로 초기화된 것을 의미한다.
21 ~ 27번째 줄 : arr은 N개의 물건만큼 (각 물건의 무게, 각 물건의 가치)를 의미한다.
위의 예시를 예로들면, arr은 [[6, 13], [4, 8], [3, 6], [5, 12]]을 의미한다.
29 ~ 40번째 줄 : DP의 점화식을 이용하여 각 물건과 무게에 대한 가치를 설정한다.
42번째 줄 : 따라서, 결국 dp[N][K]는 최대 가치에 해당하는 값이기 때문에 이 값을 리턴해주면 된다.

배낭 문제는 크게 두 가지로 나눌 수 있다.

위에서 설명한 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)와

물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)으로 나눌 수 있다.

간단하게 두 경우를 설명하자면,

① 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)은

위에서 설명한대로 동적계획법(Dynamic Programming : DP)를 이용하여 해결할 수 있고,

② 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)은

가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식인 탐욕(Greedy) 알고리즘으로 해결할 수 있다.

+ 나중에 ② 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem) 알고리즘 문제를 풀게 된다면, 그 때 더 자세히 글을 쓸 예정입니다.