[Algorithm(C++)] 다이나믹 프로그래밍, 배낭 문제 (백준 12865)

다이나믹 프로그래밍(Dynamic Programming, DP)

여러개의 하위 문제를 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

하나의 문제는 단 한 번만 풀도록 하는 알고리즘

ex) 분할 정복 기법으로 피보나치 수열을 구현한다고 생각해보자. 피보나치 수열에서 f(4)를 계산할 때 f(2)를 중복 계산하는 비효율이 발생한다.

 

다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하고 있는 큰 문제에서도 동일하다.

 

메모이제이션 사용.

메모이제이션이란?

이미 계산한 결과는 배열에 저장함으로서 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면된다.

ex) 다이나믹 프로그래밍(동적 계획법)으로 피보나치 수열을 푸는 경우에는 점화식을 활용하여 배열에 그 값을 저장해 놓을 수 있다.

 

사실 피보나치 수열로 생각하면 쉽게 이해되는데 문제에 쓰려고 하는 순간에는 어떻게 활용해야하는건가 싶다.

 

동적 계획법에 속하는 배낭 문제(Knapsack)에 대해 알아보면, 다른 문제를 더 쉬게 접근할 수 있을 것이다.

 

어떤 배낭이 있고 그 배낭에 넣을 수 있는 최대 무게가 K라고 하면, 배낭에 넣을 수 있는  N개의 물건이 각기 다른 가치 V를 가지고 있고, 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다.

 

배낭 문제는 Fractional Knapsack, 즉 물건을 쪼갤 수 있어 가치가 소수점으로 나뉘는 문제와 0-1 Knapsack, 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수형태를 가지는 두 유형으로 나뉜다.

 

Fractional knapsack의 경우는 그리디 알고리즘으로 풀 수 있다.

 

그런데 0-1 knapsack은 그리디 알고리즘으로는 최적해를 찾을 수 없다. 따라서 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다.

 

브루트포스로 푸는 방법도 있는데 가능한 모든 조합을 만들기 위해서는 시간 복잡도가 상당하기 때문에, 다른 방법을 찾아봐야 한다.

 

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

접근 방법

다이나믹 프로그래밍 방법을 사용해서 접근을 했다. (백트래킹 자체가 아직 어렵다고 생각했기 때문에..)

 

이용한 자료 구조

2차원 배열을 이용

 

풀이 방법

물품의 수는 100개로 한정되어 있기 때문에 #define MAX 100을 설정하고 두 2차원 배열을 만들어주었다.

bags 배열에 각각 가방의 무게와 가치를 입력받는다. 그리고 dp 배열에는 넣을 수 있는 물품의 무게와 현재 물품의 무게의 차이를 저장해주고, 그 전의 모든 것과 비교하는 코드를 적었다.

 

오답 코드

#include <iostream>
#define MAX 100
#define TWO 2
using namespace std;
int dp[MAX][TWO] = {{0,0}};
int bags[MAX][TWO] = {{0,0}};
int MAX_FUNC(int N, int W ){
    int max = bags[0][1];
    dp[0][0] = W - bags[0][0];
    dp[0][1] = bags[0][1];
    for(int i = 1 ; i<N;i++){
        for(int j = 0; j<i;j++){
            if( (bags[i][0] <= dp[i-j-1][0])){
                dp[i][0] = dp[i-j-1][0] - bags[i][0];
                dp[i][1] = dp[i-j-1][1] + bags[i][1];
            }
            else{
                if((bags[i][0] <= dp[i-j-1][0])){
                    dp[i][0] = dp[i-j-1][0] - bags[i][0];
                    dp[i][1] = dp[i-j-1][1] + bags[i][1];
                }else if(bags[i][0] <= bags[i-j-1][0] && dp[i-j-1][1] <= bags[i-j-1][1] + bags[i][1]){
                    dp[i][0] = bags[i-j-1][0]- bags[i][0];
                    dp[i][1] = bags[i-j-1][1] + bags[i][1];
                }else if(bags[i][0] <= W){
                    dp[i][0] = W - bags[i][0];
                    dp[i][1] = bags[i][1];
                }
            }
        }
    }
    return max;
}
int main(){
    int N, W;
    cin>> N >>W;
    for(int i = 0; i<N;i++){
        cin >> bags[i][0] >> bags[i][1];
    }
    cout << MAX_FUNC(N,W);
    return 0;
}

 

정답 풀이

가치와 물건을 저장해 놓는 배열을 따로 만든다. 

그 이후의 과정은 이외로 간단하다.

 

1) 물건을 넣을 수 없는 경우에는 dp[i-1][j]의 값을 그대로 넣는다.

2) 물건을 넣을 수 있는 경우에는 dp[i-1][j]의 값과 dp[i][j-w[i]]+v[i]의 값을 비교하여 더 큰 값을 넣는다.

이 과정을 반복했을 때 dp[n][k]의 값이 가치의 최댓값이 된다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int dp[101][100001];
int w[101];
int v[101];
int n, k;
 
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            //물건을 넣을 수 있는 경우
            if (j >= w[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            //물건을 넣을 수 없는 경우
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][k];
    return 0;
}

 

그리고 새로운 풀이를 찾았다.

위의 풀이와 매우 흡사한데 pair를 사용한다는 점이 다르다. pair의 사용법을 익히기 위해 이 방법으로도 풀어봤다.

개인적으로는 새로운 방법이 더 쉬운 것 같다.

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

#define N_MAX 101
#define K_MAX 100001
#define P pair<int, int>

using namespace std;

int K;
long long dp[N_MAX + 1][K_MAX + 1] = {0,};
vector<P > stuff;


long long dp_func(int N) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            if (stuff[i - 1].first <= j) {
                dp[i][j] = max(stuff[i - 1].second + dp[i - 1][j - stuff[i - 1].first], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int max = 0;
    for(int i = 1; i<=K;i++){
        max = (dp[N][i] > max)? dp[N][i] : max;
    }
    return max;
}


int main() {
    int N;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int v, w;
        cin >> w >> v;
        stuff.push_back(P(w, v));
    }
    cout << dp_func(N);
}

 

결국 배낭문제도 효과적인 배열은 어떤 것인지 생각하는게 제일 중요한 것 같다.

N개의 행과 K개의 열을 가진 배열을 가지고 문제를 푼다!

 

더 응용하고 싶다면 냅색문제의 확장편인 BOJ의 동전 문제를 추천한다!

https://www.acmicpc.net/problem/9084

9084번: 동전