Algorithm] Knapsack(배낭 문제) - 동적계획법

Algorithm] Knapsack(배낭 문제) - 동적계획법

처음 내가 알고리즘 문제를 접했을 때 처음으로 배낭 문제를 접근했던 방식은 그리디였다.

그리디는 다들 알고 있듯, 선택에 대한 번복도 없고, 근시안적인 선택으로 인해서

경우에 따라서는 최적해를 보장하지 못하는 문제가 발생한다.

모든 배낭 문제에 대해서 그리디가 유효한 방법이 될 수 없는 건 아니고,

물건을 임의로 쪼개어 담을 수 있는(용량을 정할 수 있는) 배낭 문제라면,

무게 당 가격을 계산해서 적당히 담는 걸 고려하여 최적해를 구할 수 있기 때문에

그리디 알고리즘으로는 해결이 가능하며 이를 부분 배낭(Fractional Knapsack)문제라고 한다.

그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다.

이 때 사용하는 방법이 동적계획법(Dynamic Programming)이다.

흔히 말해서 DP, 다이나믹이라고 불리는데

DP의 핵심은 최종해를 구하는데 이전에 구한 해를 최대한 활용한다는 것에 있다.

최종해를 바탕으로 다음 최종해를 구하는 작업을 하는 것이기 때문에,

근시안적인 선택을 하는 그리디와는 다르게 최적해는 보장할 수 있다.

물론, 어느정도 손해(속도...)는 감수해야 한다는 것. 

아주 기본적이고 제한적인 배낭 문제를

동적계획법으로 풀어봤는데, 이는 꽤 제한적이다.

#include <iostream>
using namespace std;
 
typedef struct Bag
{
    int weight;
    int value;
} Bag;
 
int maxValue(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}
 
int Knapsack(Bag arr[], int n, int maxWeight)
{
    int** DP;
    int i, j;
 
    DP = new int*[n+1];
    for (i = 0; i <= n; i++)
    {
        DP[i] = new int[maxWeight+1];
    }
 
    for (i = 0; i <= n; i++)
    {
        DP[i][0] = 0;
    }
    for (i = 0; i <= maxWeight; i++)
    {
        DP[0][i] = 0;
    }
 
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= maxWeight; j++)
        {
            if (arr[i-1].weight > j)
            {
                DP[i][j] = DP[i - 1][j];
            }
            else
            {
                DP[i][j] = maxValue(DP[i - 1][j], DP[i - 1][j - arr[i-1].weight] + arr[i-1].value);
            }
        }
    }
    return DP[n][maxWeight];
}
 
int main(void)
{
    int n, w;
    Bag* arr;
 
    cin >> n >> w;
    arr = new Bag[n];
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].weight >> arr[i].value;
    }
 
    cout << Knapsack(arr, n, w) << endl;
 
    return 0;
}

여기서 제한적이라고 했던 이유는,

작성된 동적계획법 테이블만 봐도 알겠지만

배낭의 크기가 커지고 집어 넣을 물건들이 늘어날수록

요구하는 메모리의 크기가 폭증하기 때문에 케이스가 작을 때 유용하게 써먹을 수 있다.

처음 물건의 종류 수와, 배낭 무게를 입력 받고

물건의 무게와 값어치를 순차적으로 입력받고 알고리즘을 수행한다.

DP 테이블을 구성하는 핵심 파트는 아무래도, 

if (arr[i-1].weight > j)
{
    DP[i][j] = DP[i - 1][j];
}
else
{
    DP[i][j] = maxValue(DP[i - 1][j], DP[i - 1][j - arr[i-1].weight] + arr[i-1].value);
}

이 부분이다.

Bottom Up 방식으로 구성해나가는 동적계획법의 핵심 부분으로

무게에 맞는지 아닌지 구분해보고 집어 넣을 수 있는 물건을 찾아낸다면,

그리디라면 정렬된 조건이라는 하에, 무조건 집어넣었겠지만,

이 경우에는 이것이 최적해인지 고려하고 집어 넣는 방식으로 진행된다.