📌 알고리즘 - 배낭 문제 개념

배낭 문제란?

배낭에 담을 수 있는 무게의 최대값($K$)이 정해져 있을 때 일정한 가치($V$)와 무게($W$)를 가진 짐을 배낭에 넣을 때 가치의 합이 최대가 되도록 배낭에 넣을 짐을 찾는 문제이다.

배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다.

완전 탐색

짐의 개수가 $N$일 때 가능한 부분집합의 개수는 $2^N$개이다. 따라서 시간복잡도는 $O(2^N)$이다.
⇒ 너무 느리다.

동적계획법

$D[i,w]$ = 배낭의 무게 한도가 $w$이고, $1$부터 $i$번째 짐까지 배낭에 넣을 수 있을 때 얻을 수 있는 최고 가치

DP식 $D[i,w]$를 위와 같이 정의했을 때 점화식은 아래와 같다.

2중 반복문으로 구현하면 되고, 시간복잡도는 $O(NW)$이다.

for (int i = 1; i <= N; i++) {
	for (int w = 0; w <= W; w++) {
		if (w - W[i] >= 0) {
			dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - W[i]] + V[i]);
		}
		else {
			dp[i][w] = dp[i - 1][w];
		}
	}
}