0/1 냅색 ( 0/1 knapsack problem )

Table of Contents

개요

풀이

구현

더 알아보기 : 공간 복잡도 최적화

1. 개요

 냅색 문제 ( 배낭 문제 ) 는 프로그래밍계에서 유명한 문제로서 요약하면, 담을 수 있는 무게의 최댓값이 있는 배낭, 그리고 무게와 가치를 가진 짐들이 있을 때 배낭에 넣을 짐들의 가치가 최대가 되도록 배낭에 넣을 짐들을 고르는 문제입니다.

 이 문제는 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나뉩니다. 이 중 쪼갤 수 없는 경우는 0/1 배낭 문제 ( 0/1 knapsack problem ) 이라고 불리며 동적 계획법으로 해결이 가능합니다.

 아래의 링크를 통해 0/1 배낭 문제의 예시를 보고 코딩한 후, 채점해 볼 수 있습니다. 아래의 풀이와 구현은 이 문제를 기준으로 설명하므로 반드시 읽어보시길 바랍니다.

[BOJ 1535] 안녕

2. 풀이

 초기 체력 99 = 배낭의 용량 ( 체력이 0이 되어도 죽기 때문에, 체력을 99로 잡도록 하겠습니다.)

 소모되는 체력 = 짐의 무게

 얻는 기쁨 = 짐의 가치

 위와 같이 생각하면, 0/1 배낭 문제와 같은 문제임을 알 수 있습니다. 한정된 무게내에서 최대의 가치를 뽑아내는 문제이지요.

 dp [ i ] [ j ] = 짐이 1 ~ i 번까지만 있으며, 배낭의 용량이 j일 경우의 정답.

 0/1 배낭 문제는 이와 같이 dp를 정의하면 문제를 해결할 수 있습니다.

 일단, 최종 정답이 dp[n][99] 임은 자명합니다. 남은 건 관계식인데, 경우의 수를 'i 번째 짐을 넣지 않았을 때'와 'i 번째 짐을 넣었을 때' 로 나누면 쉽게 구할 수 있습니다.

 i 번째 짐을 넣지 않았을 때 = dp [ i-1 ] [ j ] 에 그 답이 저장되어 있습니다.

 (짐이 1 ~ i-1 번까지만 있으며 배낭의 용량이 j일 경우의 정답. 과 같은 상황이기 때문입니다.)

 i 번째 짐을 넣었을 때 = dp [ i-1 ] [ j- (i 번째 짐의 무게) ] + (i 번째 짐의 가치) 를 통해 구할 수 있습니다.

 (배낭에서 i 번째 짐을 뺐을 때 남은 짐들의 가치의 최댓값을 생각해 보면 dp [ i-1 ] [ j- (i 번째 짐의 무게) ] 가 되기 때문입니다.)

 따라서 아래와 같은 식이 성립하며, 간단한 dp 구현으로 구현할 수 있습니다.

 dp [ i ] [ j ] = max( dp [ i-1 ] [ j ], dp [ i-1 ] [ j- (i 번째 짐의 무게) ] + (i 번째 짐의 가치))

3. 구현

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
 
using namespace::std;
 
int n;
int dp[25][105];
int cost[25];
int value[25];
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&cost[i]);
    for(int i=1; i<=n; i++) scanf("%d",&value[i]);
    for(int i=1; i<=n; i++){
        for(int j=0; j<=99; j++) dp[i][j] = dp[i-1][j];
        for(int j=cost[i]; j<=99; j++)
            dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]]+value[i]);
    }
    printf("%d",dp[n][99]);
    return 0;
}
 

4. 더 알아보기 : 공간 복잡도 최적화

 dp [ i ] [ j ] 를 구하는 시점에서 보면, dp [ 0 ~ i-2 ] 구간은 앞으로 필요가 없는 부분이 됩니다. 이 점을 활용해 아래와 같이 메모리를 절약할 수 있습니다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
 
using namespace::std;
 
int n;
int dp[2][105];
int cost[25];
int value[25];
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&cost[i]);
    for(int i=1; i<=n; i++) scanf("%d",&value[i]);
    for(int i=1; i<=n; i++){
        int i0 = i%2, i1 = 1-i0;
        for(int j=0; j<=99; j++) dp[i0][j] = dp[i1][j];
        for(int j=cost[i]; j<=99; j++)
            dp[i0][j] = max(dp[i0][j], dp[i1][j-cost[i]]+value[i]);
    }
    printf("%d",dp[n%2][99]);
    return 0;
}

i 가 짝수일 경우엔 dp [ 0 ] , 홀수일 경우엔 dp [ 1 ] 에 값을 저장하는 식으로 번갈아 사용하는 식입니다.