Knapsack
Knapsack 문제(=배낭 문제)는 담을 수 있는 최대 무게가 있는 배낭과 각각의 무게와 가치가 주어진 물건들의 집합에 대해서
배낭에 담은 물건의 가치가 최대가 되도록 하는 집합을 찾는 문제이다.
백준 단계별로 풀어보기 DP에 있는 문제로 G5라는 난이도를 가지고 있는데 너무 저평가된 문제인 것 같다.
우선 물건이 분할이 가능한 경우가 있는데 이 때는 가성비가 가장 좋은 물건을 순서대로 넣는 그리디 문제가 된다.
그리고 보통 접하게 될 배낭 문제는 물건을 넣거나 빼는 것만 가능하고 이를 0-1 배낭 문제라고 부른다.
우선 백준 12865번 평범한 배낭 문제로 예시를 들면
N개의 물건이 주어지고, 각 물건은 무게 W와 가치 V를 가진다.
배낭은 K만큼의 무게 제한이 있고 각 물건은 1개씩만 존재한다.
1
2
3
4
5
6
4 7
6 13
4 8
3 6
5 12
이것이 문제의 예제이다.
우선 그리디하게 접근을 해서 가장 가치가 큰 물건들부터 집어넣으면 어떻게 될까?
가장 가치가 큰 것은 무게 6에 가치가 13인 물건이다.
하지만 무게 제한 7에 대해서 이것이 최적일까 보면 (4, 8), (3, 6)인 물건의 가치 합은 14로 13보다 크다.
그렇기에 그리디한 접근으로 풀 수 없다는 것은 알 수 있었다.
1년 전에 이 문제를 처음 봤을 때 n+1크기의 1차원 배열을 만들고 0부터 넣을 수 있는지 채우는 방법을 생각했었다.
1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
cin >> a >> b;
for(int j=0;j<=m;j++){
if(j-a>=0){
dp[j]=max(dp[j-a]+b, dp[j]);
}
}
}
이런 식으로 넣어서 j위치에서 물건 a를 넣을 수 있는지를 체크하는 방법이었다.
하지만 이렇게 했을 때 a가 들어가서 dp[a]에 b가 쓰이고 dp[2*a]에는 b+b가 쓰이게 된다.
그렇게 물건이 1개만 있다는 조건을 만족하지 못하게 되었고, 고민을 했었다.
고치는 방법은 간단한데 그냥 j의 반복문을 m에서부터 0으로 내려오게 하면 된다.
논리는 똑같이 무게 a, 가치 b인 물건을 받으면서 무게 j에 대해 j-a위치에서 b를 더하면 이득인지 확인하는 것이다.
1
2
3
4
5
6
for(int i=0;i<n;i++){
cin >> a >> b;
for(int j=m;j>=a;j--){
dp[j]=max(dp[j-a]+b, dp[j]);
}
}
이렇게 많이 풀린 문제들 특징이지만 인터넷 블로그들도 복제하고 복제된 코드들이 넘쳐나기에 dp 2차원 풀이가 많다.
개인적으로는 더 떠올리기는 어려운 아이디어라고 생각을 한다.
위의 dp 배열을 2차원으로 확장해 x좌표는 여태까지 본 물건의 개수로 놓는 것인데 문제 풀이 방법을 이해하는 것에는
도움이 될 수도 있겠지만 문제를 딱 보고 떠올리기에는 직관적이지 않은 부분이 있다고 느꼈다.
두 방법은 최종적으로 O(NK)의 시간복잡도를 가지고, 공간 복잡도 측면에서 당연히 1차원 dp 배열이 이득이므로
앞으로는 위의 코드를 가지고 이해를 하겠다.
그러면 이것이 가장 기초적인 knapsack 문제였고 12920 평범한 배낭 2 문제를 보자.
문제가 크게 바뀐 것은 없고, N개의 물건이 주어지고, 각 물건은 무게 V와 만족도 C를 가진다.
이 때 각 물건은 K개씩 있고, 가방의 최대 무게는 M개이다.
우선 위에서 했던 방법처럼 접근을 하면?
1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
cin >> a >> b >> c;
for(int x=1;x<=c;x++){
for(int j=m;j>=a;j--){
dp[j]=max(dp[j-a]+b, dp[j]);
}
}
}
이렇게 개수를 입력 받고, 그 개수만큼 물건들에 대해서 계산을 해주면 된다.
하지만 이 때의 시간복잡도는 O(NMK)가 되고 문제 제한에서 시간 초과가 발생한다.
그러면 어떻게 효율적으로 모든 개수를 판단할 수 있을까 생각하면
1, 2, 4, 8.. 이렇게 이진수의 합으로 모든 정수를 만들 수 있다는 아이디어를 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0;i<n;i++){
cin >> a >> b >> c;
ll x=1;
while(c>0){
x=min(x, c);
c-=x;
for(int j=m;j>=a*x;j--){
dp[j]=max(dp[j-a*x]+b*x, dp[j]);
}
x*=2;
}
}
for(int i=0;i<=m;i++){
ans=max(ans, dp[i]);
}
cout << ans;
이렇게 x를 1부터 시작해서 1, 2, 4.. 2배씩 늘리며 확인을 한다
c보다 커지기 전까지 확인하는 테크닉을 통해서 물건의 개수 K개를 O(logK)에 확인이 가능하다.
그러면 시간복잡도가 O(NMlogK)로 시간 안에 해결할 수 있다.
원래는 bit masking을 이용한 다른 판단 방법도 쓰려고 했는데 그것은 따로 bit masking을 이용한
dynamic programming에 대한 이야기가 될 것 같아서 이렇게만 배낭 문제는 정리를 끝냈다.