- DP 와 Knapsack Problem
: 배낭 문제는, 어떤 한 사람이 갖고 있는 배낭이 있고, 그 배낭에 담을 수 있는 최대 용량이 주어지며, 이 최대 용량에 한해서, 여러개의 물건들을 집어넣고자 할때, 최대한의 가치를 뽑아내는 방법을 찾는 문제이다.
각 물건들은 무게와 값어치가 명시되어 있고 이들 중에서 배낭에 넣을 수 있으면서, 최대의 값어치를 뽑아내는 경우의 수를 찾아내면 되는 문제이다.
배낭 문제는 다시 말하면 '여러 물건이 있을때, 특정한 조건을 만족하는 조합을 구하는 문제' 라고 볼 수 있다.
배낭 문제는 두가지 유형으로 나뉜다.
물건(짐) 을 쪼갤 수 있는 경우와 물건을 쪼갤 수 없는 경우의 두 유형으로 나뉘는데,
전자의 경우 '분할가능 배낭문제' (Fractional Knapsack Problem) 라고 부르고
후자의 경우 '0-1 배낭 문제' (0-1 Knapsack Problem) 라고 부른다
또한 전자의 경우 그리디로 다항 시간안에 풀 수 있으나
후자의 경우 보통 DP 를 이용한다
알고리즘 문제를 풀때 보통 DP 로 해결해야 되는 경우가 많다.
아래는 가장 대표적인 배낭 문제 (백준 12865 - 평범한 배낭) 이다.
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
이 문제를 풀기위한 DP 2차원 배열은 다음과 같이 정의될 수 있다.
DP[i][j] : 처음부터 i번째까지 물건들을 살펴보고, 배낭의 용량이 j 일때 배낭에 들어간 물건들의 가치의 합의 최대값
그러므로 문제에서 찾으라는 답은 DP[N][K] 에 있을것이라 볼 수 있다.
DP[N][K] 의 의미가 처음 물건부터 마지막 N 번째 물건들 까지 살펴보고, 배낭의 용량이 K 일때, 배낭에 들어간 물건들의 가치의 합의 최대값이 되기 때문이다.
이때 DP 배열에 대한 점화식을
DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - weight[i]] + value[i]) 으로 생각할 수 있다
이 점화식의 의미는, 처음부터 i - 1 번째 까지의 물건들을 살펴보고 배냥용량이 j 일때 배낭에 들어간 물건들의 가치의 합의 최대값 과 처음부터 i - 1 번째 까지의 물건들을 살펴보고, i 번째 물건을 배낭에 넣었을때 가치의합의 최대값 들 중 큰값을 dp[i][j] 에 넣는다 가 된다.
i 번째 물건의 무게는 weight[i] 이며, i 번째 물건의 가치는 value[i] 이다.
배낭 문제는 이것처럼 i번째 물건을 넣었을때와 안넣었을때 가치의합의 최댓값을 골라내면 되는 그런 방식으로 접근하면 된다.
그래서 이거를 코드로 작성하면 아래와 같이 쓸 수 있다.
- C++
|
#include <iostream>
#define MAX 101
#define MAX_K 100001
using namespace std;
int N, K;
int weight[MAX], value[MAX];
int dp[MAX][MAX_K];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> K;
for (int i = 1; i <= N; ++i)
cin >> weight[i] >> value[i];
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= K; ++j) {
if (j - weight[i] >= 0) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[N][K];
return 0;
}
|
cs |
else 부분은 배낭에 i 번째 물건을 넣을 수 없는 경우, 배낭의 용량 j 는 그대로 두고 i 번째 물건은 넣지 않은 값
dp[i - 1][j] 로 그대로 넣는다.
여기서 한단계 더 생각해서 2차원 배열 대신 1차원 배열로 처리할 수 도 있다.
위의 코드는 배낭의 용량을 j = 1 ~ j = k 까지 오름 차순으로 돌려보는 방식이라면,
이번에는 역으로 j = k ~ j = 1 으로 내림차순으로 돌려보는건 어떨지 생각해보면 된다.
문제의 예제 입력 1 을 기준으로 생각해보자
N = 4, K = 7 일 때 다음과 같이 입력이 들어온다.
| weight[i] | value[i] | |
| 1번 물건 | 6 | 13 |
| 2번 물건 | 4 | 8 |
| 3번 물건 | 3 | 6 |
| 4번 물건 | 5 | 12 |
이때 1번 물건을 넣는다 치면, 배낭의 용량을 내림차순으로 돌려본다 했으므로
- 1번 물건
j = 7 일때) dp[7] = max(dp[7], dp[7 - weigth[1]] + value[1])
j = 6 일때) dp[6] = max(dp[6], dp[6 - weight[1]] + value[1])
j = 5 일때) dp[5] = max(dp[5], dp[5 - weight[1]] + value[1])
......
1번 물건을 넣고 난 후, dp 테이블은 아래와 같이 된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1번물건 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
다음으로 2번 물건을 넣는다치면
- 2번 물건
j = 7 일때) dp[7] = max(dp[7], dp[7 - weight[2]] + value[2])
j = 6 일때) dp[6] = max(dp[6], dp[6 - weight[2]] + value[2])
j = 5 일때) dp[5] = max(dp[5], dp[5 - weight[2]] + value[2])
......
2번 물건을 넣고 난 후, dp 테이블은 다음과 같이 갱신된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 2번물건 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
이런식으로 쭉 4개의 물건 다 해보면 최종적으로는 아래 처럼 된다
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 최종 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
따라서 답이 14가 된다.
- C++
|
#include <iostream>
using namespace std;
int N, K;
int dp[100001];
int weight[101], value[101];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> K;
for (int i = 1; i <= N; ++i) cin >> weight[i] >> value[i];
for (int i = 1; i <= N; ++i)
for (int j = K; j >= 1; --j)
if (j - weight[i] >= 0)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
cout << dp[K];
return 0;
}
|
cs |
아래의 백준 결과표를 보면 상당한 차이를 가져옴을 볼 수 있다.
- 다른 냅색 문제들
1) BOJ 7579 - 앱 : www.acmicpc.net/problem/7579
2) BOJ 1943 - 동전 분배 : www.acmicpc.net/problem/1943
- References)
1. chanhuiseok.github.io/posts/improve-6/
2. ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C