Dynamic Programming - Knapsack Algorithm(배낭 알고리즘)

배낭 알고리즘

 

배낭 알고리즘은 크게 2가지로 나뉜다.

 

1) 분할 가능 배낭 문제 (Fractional Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼개서 담을 수 있을 때

 

2) 0 - 1 배낭 문제 (0 - 1 Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼갤 수 없을 때

 

1번 경우는 보통 그리디 알고리즘으로 해결한다.

뭐.. 풀어보진 않았지만 가치가 높은 물건을 최대한 많이 쪼개서 넣으면 되겠죠?

 

문제는 2번 경우이다.

사실 0 - 1 배낭 문제는 NP - Complete 문제에 속한다.

알린이라도 NP-Complete는 한 번쯤은 들어봤을 것이다. 

내 기억에 NP-Complete 문제 중 하나라도 다항 시간 안에 해결할 수 있다면 모든 NP 문제를 다항 시간에 해결할 수 있고 어쩌구 저쩌구 ... 지난 학기에 배워서 기억이 잘 안 나네요ㅎㅎ

 

어쨌든! 중요한 건 이 문제는 Dynamic Programming 알고리즘으로 해결해야 한다.

(너무 기승전결이 없는 것 같지만..)

 

배낭 알고리즘은 여러 가지 예시가 가능하다. 

우리가 가장 많이 본 예시는 아래와 같을 것이다.

 

"나는 도둑이다. 

지금 도둑질을 하려고 보석방에 침입했다.

가방이 담을 수 있는 무게는 정해져 있고, 각 보석의 무게와 가치(가격) 역시 정해져 있다. 

나는 최대 얼마만큼의 돈을 벌 수 있을까?"

 

(아래의 사진은 진짜 많이 봤을 것이다. AI 쪽에서도 배낭 알고리즘이 다뤄지기 때문에)

 

우리는 이런 사람들을 "극한의 이득충"이라고 한다.

 

왜 이런 사람들을 도와줘야 하는지 모르겠지만 알고 있으면 언젠간 써먹을 날이 올 테니 공부해보자.

 

아이디어

 

이 알고리즘의 아이디어 자체는 간단하다.

 

"각 보석마다 보석이 가방에 들어갈 수 있다면, 이 보석이 들어가야지 이득인지 아닌지를 판단한다"이다.

 

말은 쉽다.. 말은 쉬운데.. 

 

조금 더 DP 스럽게 설명해보면 다음과 같다.

 

만약

 

N번째 보석이 정답에 포함되지 않는다면, N-1번째까지의 보석들 중 최선의 선택이 정답이 된다.

 

N번째 보석이 정답에 포함되어야 한다면, N-1번째까지의 보석들 중 최선의 선택과 N번째 보석이 정답에 포함된다.

이때 주의해야 할 점은 N번째 보석이 들어가도 가방은 터지면 안 된다!

 

오.. 뭔가 DP 스러워졌다.

이전까지의 경우가 중요해졌고, 이전까지의 과정을 저장하고 있어야 한다는 것 또한 알 수 있다.

 

그럼 이 말을 점화식으로 표현해보자.

수식 프로그램으로 만들었는데.. 더 이해하기 어려워 보이네^^

 

위의 수식에서 i = i번째 보석, w(i) = i번째 보석의 무게, v(i) = i번째 보석의 가치를 말한다.

(이 부분에 유의하여 수식을 다시 한번 살펴보면 좋다.)

 

여기서 헷갈릴 수 있는데 시간을 두고 깊이 고민해봐야 한다.

나도 이 부분을 제대로 이해하려고 충분한 시간 동안 멍을 때렸다.

 

이 수식에서 dp[i,w]는 가방의 최대 무게가 w일 때 i번째 보석까지의 보석들을 사용하여 만든 최선의 선택(최대 가치)이 저장되어 있는 것이다.

따라서 최선의 선택이 위에서 설명했듯이 i번째 보석이 포함되느냐 안되느냐로 갈라지게 되고, 각각의 경우가 위의 식과 같이 구해진다는 것이다.

 

즉, i번째 보석이 가방에 들어갈 수 있다면 이 친구가 들어가는 게 최선인지 아닌지를 앞에 구했던 최선의 선택과 비교해서 찾아낸다는 것이다.

 

앞에 구했던 최선의 선택이라.. 너무 DP다. 그쵸?

 

간단하게 코드로 나타내면 다음과 같다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= W; j++) {  // 여기서 W란 가방의 최대 무게
		if (w[i] > j) dp[i][j] = dp[i - 1][j];
		else dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
	}
}

 

 

배낭 알고리즘을 제대로 이해했다면 위의 코드를 이해하는 건 어렵지 않다.

코드를 봐도 이해가 안 된다면 아직 배낭 알고리즘을 확실히 이해한 게 아니기 때문에 다시 한번 고민해봐야 한다.

(내가 그랬거든요ㅎㅎ)

 

이렇게 Knapsack 알고리즘에 대해 알아보았다.

Dynamic Programming 자체도 어렵지만 이렇게 한번 더 생각해야 하는 문제는 진짜.. 싫다😭