[냅색] Knapsack Problem

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

12865번: 평범한 배낭

위 문제는 0-1 냅색-개수1로 고정된 문제이다. 위 문제를 보기전에 냅색의 종류부터 보자.

기본적인 냅색은 크게는 두가지 특징으로 분류된다.

1) 물건을 쪼갤 수 있는가 -> 그리디

2) 물건의 개수가 무한대인가, 1개인가 -> dp

 

<1>

물건을 쪼갤 수 있는 냅색(Fractional Knapsack Problem) 문제는 남은 가방의 크기를 '자원'으로 생각하고,

물건을 선택할때에 자원 대비 가치를 최대화해야한다.

한마디로, (가치/무게)가 높은순으로 넣어주기만 하면 끝난다.

물건의 개수가 정해져있다면 별개로 카운팅해주고, 무한대라면 개수는 신경쓰지 않으면 된다.

 

<2>

물건을 쪼갤 수 없을때에 이를 0-1 Knapsack이라 한다.

이 물건을 선택하거나(1), 선택하지 않거나(0)이기 때문에 저러한 이름이 붙은것이다.

글의 맨 위에 등장했던 BOJ[12865] 평범한 배낭 문제를 보면, 물건을 쪼갤 수 없고 개수가 1개인 냅색임을 알 수 있다.

물건을 쪼갤 수 없을때에는 다이나믹프로그래밍으로 해결하는것이 기본인데,

물건의 개수가 무한대일때에는 평범한 바텀업 dp로 해결이 가능하다.

 

다만, 물건의 개수가 1개로 고정 되었을때에는 어떻게 해결할 수 있을까? 아래에 BOJ[12865]의 소스코드를 첨부한다.

#include<stdio.h>
int w[101],v[101],dp[100001];
int main(void) {
    int i, j, n, k;
    scanf("%d %d", &n, &k);
    for (i = 0; i < n; i++)
        scanf("%d %d", &w[i], &v[i]);
    for (i = 0; i < n; i++)
        for (j = k; j >=w[i]; j--)
            if (dp[j] < dp[j - w[i]] + v[i])
                dp[j] = dp[j - w[i]] + v[i];
    printf("%d", dp[k]);
    return 0;
}

물건의 무게와 가치를 입력받고, dp[k]를 출력하도록 dp를 채워넣어야 한다.

8-11라인까지 for문으로 구성되어 있으니 바텀업 dp라고 볼 수 있는데

9라인의 for문이 역방향이다

물건의 개수가 무한대인 것과, 1개인것의 차이는 바텀업 dp의 순회가 정방향이냐 역방향이냐의 차이이다.

위 코드에서 9라인의 for를 정방향으로 바꾸면 '쪼갤 수 없고 개수가 무한대인 냅색'의 해가 나온다.

 

정방향으로 dp를 순회하게 되면, 비록 하나의 물건을 선택했을 지라도, 이를 dp[k]~dp[w[i]]까지 전부 갱신하는 도중 

이미 해당 물건을 선택해서 갱신된 dp값을 재참조하는 경우가 생긴다.

개수가 무한대라는 것은 '개수가 정답에 영향을 미치지 않는' 것이므로 상관없지만,

개수가 1개로 고정된것을 무한대일때처럼 처리해주기 위해서는 역방향으로 탐색을 하여, 최대 한번만 갱신하도록 해야한다.

dp를 갱신할때 항상 참조하는 값은 왼쪽에서 온다. 그래서 오른쪽에서 시작하게되면 중복이 발생하지 않는다.

 

결론

1. Fractional Knapsack : (가치)/(무게)를 우선순위로 큰것부터 삽입

2. 0-1 Knapsack : 바텀업 dp + 개수가 한개라면 역방향, 무한대라면 정방향 

 

개수1개 냅색->역방향 바텀업... 꼭 기억하자

 

 

 

+) 개수가 한개가 아니라면?

이 문제를 보자https://www.acmicpc.net/problem/12920

12920번: 평범한 배낭 2