티스토리 뷰

반응형

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. 구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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;
}
 
cs




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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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;
}
cs


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

반응형

'문제 풀이' 카테고리의 다른 글

printf 문제 풀이  (0) 2017.11.30
최장 증가 부분 수열 ( LIS )  (0) 2017.11.15
[BOJ 8462] 배열의 힘  (0) 2017.11.11
[BOJ 13548] 수열과 쿼리 6  (0) 2017.11.11
[BOJ 13518] 트리와 쿼리 9  (0) 2017.11.03