[C++] 배낭 문제 (KnapSack Problem)

안녕하세요 오늘은 배낭 문제 알고리즘에 대해 알아보겠습니다.

배낭 문제는 주어진 N개의 아이템 중에서 무게 W까지 넣을 수 있는 배낭에 최대 이익 V가 되도록 고르는 알고리즘이에요.

 

배낭 문제는 직관적으로 이해하기 힘든 dp 알고리즘 중 하나인데요.

정확하게 말하면 0-1 배낭 문제가 어렵고 분할가능한 배낭 문제는 그나마 괜찮습니다.

 

우선 두 문제 모두 "무게 한도 안에서 최대 이익을 갖도록 아이템을 선택한다"는 점은 같습니다.

0-1은 물건을 넣거나(1) 넣지 않거나(0) 둘 중 하나인 반면 fractional은 물건을 분할할 수 있다는 점이 달라요.

아래에서 천천히 알아보겠습니다.

---

분할가능한 배낭 문제 (Fractional KnapSack Problem)

분할가능한 배낭 문제에서는 주어진 아이템을 더 작은 무게로 분할할 수 있습니다.

 

예시에서는 최대 하중이 10w인 가방과 아이템 5개가 주어졌네요.

v는 아이템의 이익, w는 아이템의 무게입니다,

 

fractional에서는 아이템을 분할할 수 있다고 했는데요.

그렇다면 가장 이익이 가장 커지도록 아이템을 선택하는 방법은?

 

무게 대비 이익(v/w)이 큰 아이템 순으로 집어 넣으면 됩니다.

각 아이템의 v/w를 구해볼게요.

빨간색으로 표시한게 v/w입니다.

예시에서는 3번, 5번, 1번, 2번, 4번 순으로 집어넣으면 되겠네요.

만약 v/w가 같은 아이템이 있다면 서로 순서는 무관합니다.

 

2번까지 모든 아이템을 집어 넣었습니다.

현재 이익은 22이고 무게는 8w에요.

그럼 마지막 4번 아이템을 남은 2w만큼만 잘라서 가방에 넣어줄게요.

결과적으로 24v / 10w인 가방이 되었습니다.

 

분할가능한 배낭 문제는 구현이 간단하기 때문에 C++ 구현은 넘어가도록 하겠습니다.

여러분들이 생각하시는 그 구현이 맞아요.

 

---

0-1 배낭 문제 (Zero-One KnapSack Problem)

0-1 배낭 문제에서는 아이템을 분할할 수 없습니다.

 

구현과 함께 설명을 해볼게요,

우선 dp 테이블은 하중 제한이 K인 배낭일 때 1번부터 N번째 아이템까지 고려한 최대 이익으로 정의할 수 있어요

2차원 배열이고 x축은 고려하는 아이템의 번호 n, y축은 하중 제한 k, 원소의 값은 정의와 같습니다.

 

dp 테이블을 채우는 방법은

n-1번 째 아이템이 k일 때 이익과 n-1번 째 아이템이 k-w일 때 이익 + 현재 아이템의 이익 v 중 더 큰 값을 고르면 됩니다.

 

물론 이해를 다 하셨겠지만 보충 설명을 해볼게요.

아까와 같은 예시입니다.

 

아래 테이블은 0번째 아이템을 고려한 상태에서 1번째 아이템이고 하중 제한이 2일 때를 고려하는 중이에요.

이 경우에는 3이 크니까 3이 들어갑니다.

 

아래의 경우에는 5와 13 중에 13이 들어가겠네요.

 

모든 과정을 거치면 아래처럼 됩니다.

 

구하는 값은 4행 10열에 있는 22가 되겠네요.

 

이해가 되셨나요?

원소를 채울 때 두 선택지는 물건을 넣을 수 있으면 넣을지 또는 물건을 넣지 않고 이전의 최적값을 가져올지로 바꿔 말할 수도 있어요.

 

C++ 코드 보겠습니다.

// N: 아이템의 개수
// K: 배낭의 최대 하중
// W: 아이템의 하중
// V: 아이템의 이익
// wv: dp 테이블

cin >> N >> K;

// 0번 아이템은 따로 처리
cin >> W >> V;
for (int k = W; k <= K; ++k)
	wv[0][k] = V;

for (int n = 1; n < N; ++n) {
	cin >> W >> V;

	for (int k = 0; k <= K; ++k) {
		// 이전의 최적값과 아이템을 넣은 값 중에서 선택
		int v = wv[n - 1][k];
		if (k >= W) v = max(wv[n - 1][k - W] + V, v);

		wv[n][k] = v;
	}
}

cout << wv[N - 1][K];

 

학교 교수님 설명을 들을 때는 뭔가 더 잘 설명할 수 있었을 것 같았는데 막상 설명하고 보니 미묘하네요.

이해가 안되는 부분이 있다면 댓글로 편하게 질문주세요.

 

도움이 되셨다면 하트와 댓글 부탁드립니다.