냅색 (Knapsack)

안녕하세요.

오늘은 냅색 (knapsack) 에 대해 알아보겠습니다.

---

개념

출처 : https://pixabay.com/ko/

냅색은 일명 배낭 채우기 문제라고도 불립니다.

N개의 물건은 각각 무게 w와 가치 v를 가짐
배낭이 버틸 수 있는 최대 무게는 weight_limit

weight+limit를 넘지 않도록 배낭에 물건을 넣어서 가치가 최대가 되게 하는 문제

---

Brute Force

모든 경우의 수를 찾는 브루트 포스 알고리즘을 생각해봅시다.

 

해당 물건을 가방에 넣을지 말지 2가지 경우의 수가 있습니다.

물건이 N개가 있으니 최종 시간 복잡도는 O(2 ^ N) 입니다.

 

N이 30만 되어도 10억을 넘는 숫자가 되니 더 빠른 알고리즘을 생각할 필요가 있습니다.

---

Dynamic Programming

동적 계획법으로 문제를 풀려면, 최적의 원리를 만족해야 합니다.

최적의 원리
: 어떤 문제의 최적해가 그 문제를 분할한 부분 문제에 대한 최적해를 항상 포함하고 있으면 최적의 원리가 성립한다

 

집합 S를 n개의 물건들 중에 최적으로 고른 부분 집합이라고 가정하겠습니다.

• 집합 S가 n번째 물건을 포함하고 있다면,
  • n-1 개의 물건들 중에서 최적으로 고른 가치의 합 + n번째 물건의 가치
• 집합 S가 n번째 물건을 포함하고 있지 않다면,
  • n번째 물건을 뺀 나머지 n-1 개의 물건들 중에서 최적으로 고른 가치의 합

 

이를 점화식으로 나타내면 다음과 같습니다.

출처 : https://gsmesie692.tistory.com/113

P[i, w] = 1 ~ i번째 물건이 있고, w의 무게 제한이 있을 때 최대로 낼 수 있는 가치

vi = i번째 가치

wi = i번째 가치

 

• i번째 무게가 무게 제한 w를 넘어선다면, (wi > w)
  • i번째 물건을 뺀 i-1 개의 물건들을 가지고 구한 이전 단계의 최적값
• 그렇지 않다면,
  • Max(i번째 물건을 포함한 최적값, i번째 물건을 뺀 i-1 개의 물건들을 가지고 구한 이전 단계의 최적값)

 

Knapsack 알고리즘은 이러한 성질을 만족하기에 다이나믹 프로그래밍을 사용할 수 있습니다.

---

과정

아래 사진의 출처는 visualization 사이트인 https://monicagranbois.com/knapsack-algorithm-visualization/ 에서 가져왔습니다.

 

물건이 3개 있다고 가정하겠습니다.

1. 가치 4, 무게 2
2. 가치 3, 무게 1
3. 가치 5, 무게 3

 

가방의 무게 제한은 5라고 가정하겠습니다.

 

=> 물건 개수 x 무게 제한 만큼의 dp 테이블을 만듭니다.

---

• k == 1 일 때,
  • 현재 물건의 무게가 2, 무게 제한은 1
  • 해당 물건을 가방에 집어넣지 못함
  • P[1, 0] = 0

 

• else,
  • 현재 물건의 무게가 2, 무게 제한은 2 <= k <= 5
  • 해당 물건을 가방에 집어넣을 수 있음
  • 물건을 집어넣지 않은 가치 0과 집어넣고 나서의 4를 비교해서 더 큰 값 갱신
    max (P[0, k - w1] + v1, P[0, k]) ⇒ max(0 + 4, 0) = 4

---

• k == 1 일 때,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[1, k - w2] + v2, P[1, k]) ⇒ max(0 + 3, 0) = 3

 

• k == 2 일 때,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[1, k - w2] + v2, P[1, k]) ⇒ max(0 + 3, 4) = 4

 

• else,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[1, k - w2] + v2, P[1, k]) ⇒ max(4 + 3, 4) = 7

---

• k < 3 일 때,
  • 해당 물건을 가방에 집어넣을 수 없음
  • P[2, k]

 

• k == 3 일 때,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[2, k - w3] + v3, P[2, k]) ⇒ max(0 + 5, 7) = 7

 

• k == 4 일 때,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[2, k - w3] + v3, P[2, k]) ⇒ max(3 + 5, 7) = 8

 

• k == 5 일 때,
  • 해당 물건을 가방에 집어넣을 수 있음
  • max(P[2, k - w3] + v3, P[2, k]) ⇒ max(4 + 5, 7) = 9

 

이렇게 테이블에 값을 다 매기고 나면, P[3][5]가 정답이 됩니다.

---

시간 복잡도

O(N * M)

N : 물건의 개수

M : 가방 무게 제한

---

코드

#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))

const int SIZE = 1e5 + 4;

struct Pair {
	int w, v;
}things[104];

struct knapsack {
	int dp[104][SIZE];

	int solve(int N, int K) {
		register int i, j;
		for (i = 1; i <= N; ++i) {
			for (j = 1; j <= K; ++j) {
				dp[i][j] = dp[i - 1][j];
				if (things[i].w <= j)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - things[i].w] + things[i].v);
			}
		}

		return dp[N][K];
	}
}ks;

int main()
{
	//freopen("input.txt", "r", stdin);

	int N, K;
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; ++i)
		scanf("%d %d", &things[i].w, &things[i].v);

	printf("%d\n", ks.solve(N, K));
}

 

+) 메모리를 더 줄일 수 있습니다.

2차원 dp 테이블에서 행을 없애 1차원 테이블로 만들 수 있습니다.

 

• i번 행의 dp 값을 채우기 위해 dp[i-1, k] 값을 확인했음
  • 2차원 테이블에서 그 전 행의 값만 중요함
• 임의의 열 j를 기준으로 볼 때, 자신보다 작은 열이나 같은 값을 확인
  • max(i번째 물건을 포함한 값, i번째 물건을 포함하지 않은 값)을 dp에 넣음
  • i번째 물건을 포함한 값 : P[i-1, j - wi] 값을 확인
  • i번째 물건을 포함하지 않은 값 : P[i-1, j] 값을 확인
  • 같은 행에 대해 큰 값의 열부터 내림차순으로 dp 테이블을 채우면 1차원 테이블만 있어도 됨

#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))

const int SIZE = 1e5 + 4;

struct knapsack {
	int dp[SIZE];

	inline void solve(int K, int w, int v) {
		for (register int i = K; i >= w; --i) {
			dp[i] = max(dp[i], dp[i - w] + v);
		}
	}
}ks;

int main()
{
	//freopen("input.txt", "r", stdin);

	int N, K, w, v;
	scanf("%d %d", &N, &K);

	while (N--) {
		scanf("%d %d", &w, &v);
		ks.solve(K, w, v);
	}

	printf("%d\n", ks.dp[K]);
}

 

시간과 메모리 둘 다 줄은 모습을 확인할 수 있습니다.

---

문제

기본 문제 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

응용 문제 1 : https://www.acmicpc.net/problem/20303

20303번: 할로윈의 양아치

응용 문제 2 : https://www.acmicpc.net/problem/1943

1943번: 동전 분배

응용 문제 3 : https://www.acmicpc.net/problem/10982

10982번: 행운쿠키 제작소

---

참고 자료

knapsack 설명 : https://gsmesie692.tistory.com/113

knapsack 시각화 : https://monicagranbois.com/knapsack-algorithm-visualization/

 

감사합니다.