개발 블로그

문제 링크 : https://www.acmicpc.net/problem/12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

접근 방법

이 문제는 유명한 '배낭 문제(https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C)' 이다.

DFS를 이용한 완전탐색으로 풀었더니 시간초과가 났다. DP로 빠르게 풀어보자.

i = 1 부터 N 까지

1) 해당 물건을 배낭에 담았을 때와

2) 배낭 리미트 K를 넘어가서 해당 물건을 담지 않았을 때를

고려하여 검사를 진행한다.

DP[i][k] : 1번째 물건부터 i번째 물건까지 고려했을 때, 담을 수 있는 가장 최대 가치라고 하자.

그리고 예제에 주어진 입력으로 아래 이차원배열 DP를 채워보자.

먼저 limit가 1일 때는 아무것도 담을 수 없다. 물건들 무게가 모두 1이 넘기 때문이다. 그래서 limit=1인 열은 모두 0으로 채운다.

limit = 2일때도 마찬가지이다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

limit = 3일 때

: W[1]과 W[2]는 담을 수 없다. limit 3을 넘어가기 때문이다. 0으로 채워준다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

그러면 네번째 물건까지 고려했을 때, 담은 물건의 최대 가치는 어떻게 될까?

W[4]는 5이기 때문에 네번째 물건은 담을 수 없다. -> 그렇기 때문에 4번째 물건까지 고려하기 직전인 3번째 물건까지 고려했을 때 최대 가치인 DP[3][3]을 DP[4][3]에도 넣어주면 된다. 

limit = 4일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][4]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][4]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][4]에는 DP[2][4]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 없다. 그래서 세번째 물건까지 고려했을 때의 값인 DP[3][4]를 DP[4][4]에도 넣어준다. 

limit = 5일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][5]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][5]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][5]에는 DP[2][5]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 8보다 크기 때문에 DP[4][5]는 12로 채워준다. 

limit = 6일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][6]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][6]에는 DP[1][6]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건까지 고려했을 때 보다 가치가 더 적기 때문에 DP[3][6]에는 DP[2][6]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 13보다 작기 때문에 DP[4][6]는 DP[3][6]의 값을 그대로 채워준다. 

limit = 7일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][7]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][7]에는 DP[1][7]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 이때, 이전과는 다르게 한번 더 생각해야한다!!!

왜냐하면 만약 무게가 3인 세번째 물건을 담으면, 백팩은 무게 4가 남게 된다.

그 남은 무게에서 최대 가치는-> "limit=4이고 두번째 물건까지 고려했을 때"인 DP[2][4]가 된다. 

그리고 만약 무게가 3인 세번째 물건을 담지 않으면, 두번째 물건까지 고려했을 때의 최대 가치인 DP[2][7]의 값을 DP[3][7]에도 채워주면 된다. 

즉, 정리하면 아래 두 경우 중 더 큰 값을 DP[3][7]에 채워준다.

case 1) W[3]을 담을 경우 : DP[3][7] = DP[2][7 - W[3]] + V[3]

case 2) W[3]을 담지 않을 경우 : DP[3][7] = DP[2][7]

결론은, case 1)에서 DP[3][7]은 8+6 = 14로서,

case 2)에서 DP[2][7]인 13보다 크기 때문에 

DP[3][7]에는 14를 채워준다. 

: 네번째 물건까지 고려했을 때도 위 상황과 같이 아래의 두 경우를 고려해서 적어주면 된다. 

case 1) W[4]를 담을 경우 : DP[4][7] = DP[3][7 - W[4]] + V[4]

                                                            = DP[3][7 - 5]       + V[4]  

                                                            = DP[3][7 - 5]       + V[4]

                                                            = 0                          + 12

case 2) W[4]를 담지 않을 경우 : DP[4][7] = DP[3][7] = 14

즉, DP[4][7] = max(12, 14) = 14.

점화식으로 표현하면 다음과 같다.

DP[i][k] (최대 k무게까지 담을 수 있고, 1~i번째 물건까지 고려했을 때, 최대 가치 합) ?

1) DP[i-1][k]                                                                                         (W[i] > k) : i번째 물건 무거워서 못 담을 때

2) max( DP[i - 1][k - W[i]]   +   V[i]  ,  DP[i-1][k] )                  (W[i] <=k and i>0) : i번째 물건 담았을 때

3) 0                                                                                                    (i = 0 and k = 0)                                                                        

//
//  DFS_BOJ12865_평범한배낭.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, K;
int W[101] = {0,};
int V[101] = {0,};
int DP[101][100001];

void dp(){
    
    for(int limit = 1; limit<=K; limit++){
        for(int row = 1; row<=N; row++){
            //1. 담을 수 없을 경우
            if(W[row] > limit){
                DP[row][limit] = DP[row-1][limit];
            }
            //2. 담을 수 있는 경우
            else{
                DP[row][limit] = max(DP[row-1][limit - W[row]] + V[row]  ,  DP[row-1][limit]);
            }
        }
    }
    
}

int main(){

    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> W[i] >> V[i];
    }
    
	//초기화
    for(int r=0; r<=N; r++)
    {
        DP[r][0] = 0;
    }
    for(int c = 0; c<=K; c++){
        DP[0][c] = 0;
    }

    dp();

    cout << DP[N][K];
    
    return 0;
}