1. Knapsack Problem, 배낭문제란?
많은 예제에서 이야기하듯이, 무게와 가치로 설명을 해본다. 어떠한 아이템이 있을 때, 그 아이템은 무게와 가치라는 두 개의 값을 갖는다. 이 때, 무게는 제약조건이고, 가치는 최대로 얻고 싶은 것이다.
이러한 아이템이 여러개 있을 때, 선택한 아이템들의 가치합을 최대로 만드는 아이템들을 선택하는 것이다.
간단히 말하자면 부분집합을 찾는데, 부분집합에 조건이 따로 있다고 생각하면 된다. 그래서 브루트포스로 해당 문제를 해결하면 O(2ⁿ) 만큼, 즉 부분집합의 수 만큼 시간이 걸린다.
2. 다이나믹 프로그래밍(DP) 이용
DP는 큰 문제를 작은 문제로 나누어서 푸는 기법이다. 그 과정에서 중복되는 계산값을 Memoization 해서 시간 복잡도를 줄인다. 따라서 배낭문제를 어떻게 작은 문제로 나눠야 하는지를 먼저 생각해야 한다.
최대무게 W = 8 이라고 하고 아이템을 A, B, C, D 총 4개라고 가정한다.
NP( 확인한 아이템들, 최대무게) 의 값이 최대무게일때 갖는 최대 가치합이라고 하자. 그러면 궁극적으로, 원하는 답은 NP("ABCD", 8) 이다.
작은 문제로 나누기 위해서는 아이템을 선택할지 말지 결정해야 한다. 먼저 말로 풀어 설명한다.
ABCD 4개의 아이템을 체크했고, 최대 무게가 8일때의 최대 가치합을 구할려면 그 이전상황으로 되돌아간다. 아이템을 순서대로 집는다고 가정하면, 그 이전상황은 ABC 3개의 아이템을 체크했을 때이다.
NP("ABC", 8) 의 값은 그 이전과정을 통해서 구해졌을 것이다. 아이템 D를 봤을 때, 먼저 체크해야 할 것은 D가
담길수 있을 지 없을지 판단해야 한다. 만약 담길 수 없다면 NP("ABCD", 8) 은 NP("ABC", 8) 과 동일하다.
담길수 있다면, D를 담으면 가치가 최대가 되는지 체크해야 한다. 담았다면NP("ABC", 8-D의무게) + D의 가치가 NP("ABC",8) 보다 큰지 작은지 체크해야 한다.
NP("ABC", 8-D의무게) 가 의미하는 바는 아이템을 C까지 봤는데, 최소한 D가 들어갈 자리는 남겨놓은 최대무게 일때의 가치합의 최대이다. NP("ABC", 8-D의무게) 라고 해서 D가 들어가서 무게가 꽉 찰 수도 있고, 꽉 안 찰 수도 있다. 이 모든 과정은
NP값을 저장하기 위해 2차원 배열 혹은 1차원 배열을 사용 할 수 있다.
3. DP 구현 - 2차원 배열
예제는 백준 12865번의 입력 예제를 이용한다.
아이템은 4개이고, 최대 무게는 7이다.
| 무게 | 가치 | |
| i=1 | 6 | 13 |
| i=2 | 4 | 8 |
| i=3 | 3 | 6 |
| i=4 | 5 | 12 |
변수 설정
i의 의미는 몇번 아이템까지 체크했냐 이다. 첫번째 아이템을 선택해서 넣을지 말지 결정할 때는 체크한 아이템이 아무것도 없기 때문에 i=0 을 이용해야 한다.
dp[i][j] 는 i번째 아이템을 체크했고, 최대무게가 j일때 선택된 아이템들의 가치합의 최댓값이다.
검증
무게가 0일 때는 아무것도 집지 못하므로 계산하지 않는다. 그러나, 코드를 작성할 때, dp[i][0]을 이용하기 때문에 0으로 값을 세팅해줘야 한다.
1. 첫번째 아이템을 집을 때는 무게제한만 맞추면 된다. 최대 무게가 6일때 부터 들어갈 수 있다.
K=4 일때 dp[1][4]를 구하고 싶으면 담았을 때와 담지 않았을 때를 비교해야 한다. 담지 않았을 때의 가치는 무조건 0이고, 담았을 때는 13이다. 최댓값을 구하는 것이므로 dp[1][4] = 13 이다.
if ( 첫번째 아이템 무게 4 >= 최대무게 ) {
int 첫번째 아이템을 담지 않았을 때 = dp[1-1][최대무게]; // 첫번째 아이템을 보기전 상태를 가져온다.
int 첫번째 아이템을 담았을 때 = dp[1-1][최대무게-첫번째 아이템 무게] + 첫번째 아이템 가치;
// 위 두 값을 비교해서 큰 값을 dp[1][최대무게] 에 저장한다.
// 이 때 dp[1-1][최대무게-첫번째 아이템 무게] 은 무조건 0 이다.
// dp[1-1][최대무게] 도 무조건 0 이다.
}
그러므로 표로 나타내면 아래와 같이 결과가 나온다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
2. 두번째 아이템을 집을 때도 무게제한을 본다.
{ MAX ( 안 집었을때, 집었을 떄) }
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 |
최대무게가 1, 2, 3일때는 넣지 못한다.
그러나, 4 부터는 담을 수 있으므로 계산해야 한다.
dp[2][4] = MAX ( dp[2-1][4], dp[2-1][4-3] + 2번아이템가치) = MAX( 0, 8 ) = 8
dp[2][5] = MAX ( dp[2-1][5], dp[2-1][5-3] + 2번아이템가치) = MAX(0, 8) = 8
dp[1][K]의 값은 이미 위에 계산이 된 상태이다.
최대무게가 6일때
dp[2][6] = MAX ( dp[2-1][6], dp[2-1][6-3] + 2번아이템가치) = MAX(dp[1][6], dp[1][3] + 2번아이템가치) = MAX(13, 0+8) = 13
'dp[1][3] + 2번아이템가치' 의 의미를 알 필요가 있다.
dp[1][3] = NP( 1번 아이템까지 봤을 떄, 아이템들의 가치합을 최대로 하는 아이템들, 최대무게3 )
여기서 우리는 어떠한 아이템들이 선정되었는지, 그 선택된 아이템들의 무게합이 몇인지 알 필요가 없다. 단지, 2번 아이템을 넣어도 최대무게를 초과하지 않는 것만 알면 된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
그 다음부터는 계속 반복한다.
3번째 물건을 보았을 때 용량이 1인 가방에 못넣음
3번째 물건을 보았을 때 용량이 2인 가방에 못넣음
3번째 물건을 보았을 때 가방용량 3 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 0와 담았을 때 6를 비교한다
3번째 물건을 보았을 때 가방용량 4 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 8와 담았을 때 6를 비교한다
3번째 물건을 보았을 때 가방용량 5 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 8와 담았을 때 6를 비교한다
3번째 물건을 보았을 때 가방용량 6 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 13와 담았을 때 6를 비교한다
3번째 물건을 보았을 때 가방용량 7 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 13와 담았을 때 14를 비교한다
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| i=3 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
4번째 물건을 보았을 때 용량이 1인 가방에 못넣음
4번째 물건을 보았을 때 용량이 2인 가방에 못넣음
4번째 물건을 보았을 때 용량이 3인 가방에 못넣음
4번째 물건을 보았을 때 용량이 4인 가방에 못넣음
4번째 물건을 보았을 때 가방용량 5 >= 물건무게 5 이므로 4번째 물건을 안 담았을 때 8와 담았을 때 12를 비교한다
4번째 물건을 보았을 때 가방용량 6 >= 물건무게 5 이므로 4번째 물건을 안 담았을 때 13와 담았을 때 12를 비교한다
4번째 물건을 보았을 때 가방용량 7 >= 물건무게 5 이므로 4번째 물건을 안 담았을 때 14와 담았을 때 12를 비교한다
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| i=3 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| i=4 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
구하고자 하는 값 dp[4][7] = 14이다.
4. DP 구현 - 1차원 배열
위 계산과정에서 dp[i][j] 를 여러번 이용했다. 그러나, 자세히 살펴보면 각 반복문마다 dp[i-1][j] 만 사용했다. 그러므로, 1차원 배열로도 충분히 구현 가능하다. 즉 dp[j] 만 사용한다.
그러나, i 가 없으므로 j=K 부터 계산해야 한다.
만약 j=0 부터 계산했을 때를 보자.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| i=3 | 0 | 0 | 6 | 8 | 8 | ?????? |
i=2 까지는 큰 이상함을 못 느낄 것이다. 그러나 i=3이고 최대무게가 6일때 오류가 드러나게 된다.
2차원 배열 : 3번째 물건을 보았을 때 가방용량 6 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 13와 담았을 때 6를 비교한다
1차원 배열 : 3번째 물건을 보았을 때 가방용량 6 >= 물건무게 3 이므로 3번째 물건을 안 담았을 때 13와 담았을 때 12를 비교한다.
dp[6] = MAX ( dp[6], dp[6-3번째 아이템 무게] + 3번째 아이템 가치 ) = MAX(13, dp[3] + 3) = MAX(13, dp[3] + 3) = MAX (13, 12) = 13
dp[3]은 앞에서 이미 계산되었다. dp[3]=6 이라는 것에서 3번 아이템이 뽑혔다는 것을 알 수 있다. 그러나, dp[3-3] + 3 이 의미하는 것은 3번 아이템을 뽑는 것이다.
즉, i가 없으므로, 몇번째 아이템까지 체크했는지 알 수 없다. 원하는 dp[3]은 i=2일 때의 값인데 i=3일때의 값을 이용해버린다.
그러면 j=K부터 계산하면 결과가 동일할까?
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| i=1 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| i=2 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| i=3 | ?????? | 14 |
dp[6] 계산에 이용되는 dp[3]은 i=2 일 때 인것이 보장된다. ( 계산되지 않았으므로 )
즉, dp[j - i번째아이템무게] 에서 마이너스 연산을 하므로 항상 dp[j]는 j보다 작을 때의 dp값을 이용하게 된다. 이는 i-1 번째 계산에서 도출된 dp값만을 이용한다는 것을 의미한다.
5. 코드
1차원 배열 이용 (c++17)
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > knapsack;
int dp[100001];
int main() {
int N, K, n, v;
scanf("%d %d\n", &N, &K);
for(int i=1; i<=N; i++) {
scanf("%d %d", &n, &v);
knapsack.push_back(make_pair(n, v));
}
for(int i=1; i<=N; i++) { // i는 물건
for(int j=K; j>0; j--) { // j는 가방의 최대 용량.
if (j - knapsack[i-1].first >= 0) {
dp[j] = max(dp[j], dp[j-knapsack[i-1].first] + knapsack[i-1].second);
}
}
}
printf("%d\n", dp[K]);
}
2차원 배열 이용 (c++17)
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > knapsack;
int dp[101][100001];
int main() {
int N, K, n, v;
scanf("%d %d\n", &N, &K);
for(int i=1; i<=N; i++) {
scanf("%d %d", &n, &v);
knapsack.push_back(make_pair(n, v));
}
for(int i=1; i<=N; i++) { // i는 물건
for(int j=1; j<=K; j++) { // j는 가방의 남은 용량.
if (j - knapsack[i-1].first >= 0) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-knapsack[i-1].first] + knapsack[i-1].second);
} else { // 무게 때문에 가방에 넣을 수 없음
dp[i][j] = dp[i-1][j];
}
// printf("\n");
}
}
printf("%d\n", dp[N][K]);
}