[Algorithm]Baekjoon 12865번 :: 평범한 배낭

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

12865번: 평범한 배낭

int dp[101][100001] = { 0 };
int w[101] = { 0 };
int v[101] = { 0 };
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, k;
 
    cin >> n >> k;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }
 
    for (int i = 1; i <= n; i++) // n : 물품의 수
    {
        for (int j = 1; j <= k; j++) // k : 최대무게
        {
            if (w[i] <= j) // 물건을 담을 수 있으면,
            {
                dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]); 
            }
            else // 물건을 담을 수 없으면
            {
                dp[i][j] = dp[i - 1][j]; // 이전DP값 그대로 유지.
            }
        }
    }
 
    cout << dp[n][k];
}

유명한 0-1 냅색 문제이다. 물건을 쪼갤수없는 경우가 0-1냅색문제라고 하는데, 이럴경우 dp를 활용해야 한다.

쪼갤 수 있는 경우 Fraction Knapsack 이라고 하는데 이럴 경우에는 큰물건부터 담아보는 그리디를 활용한다고 한다.

 

dp문제를 거의 안풀어봤었던 시절에는 설명을 봐도 무슨소린지 이해가 안갔었는데 다행히 지금은 잘 이해가 된다.

dp문제들 특징?이라해야하는지 모르겠는데 로직을 글로 표현하기가 조금 어려운편이라 코드로 이해하는게 더 쉬울때가 있다.

 

이 문제같은 경우, 각 물건을 차례대로 기준으로 잡고(i) 최대무게까지 반복문을 통해(j) DP테이블을 업데이트한다.

먼저 물건을 담을 수 있는 경우, 못담는 경우가 있으며 담을 수 있을 때 또 두가지의 분기점으로 갈린다.

 

1. 물건을 담을 수 있는 경우.  두 가지를 고려해서 그 중 가치가 더 큰 값을 DP테이블에 업데이트한다.

  -> 1.1 물건을 그대로 담는다.

             현재 수용가능한 무게(j)에서 담을물건의 무게를 빼고 남은 무게(j-w[i])의 최대가치를(dp[i-1][j-w[i]) 구한다.

             그리고 이 값과 담을 물건의 가치를 더한다.  즉, dp[i-1][j-w[i] + v[i]

             물건을 포함하기 이전의 값을 가져와야하기 때 문에 i-1을 해준다.

 

  -> 1.2 물건을 담지 않는다. (담을 수 있음에도 불구하고)

            왜냐하면 담지 않고 다음 물건을 담는게 오히려 전체적인 가치를 높일 수 있는 경우가 존재할 수 있기 때문이다.

            그렇기 때문에 그냥 이전DP테이블의 값을 그대로 적용시킨다. (dp[i-1][j])

 

2. 물건을 담을 수 없는 경우

     -> 담을 수 없기 때문에 이전 DP테이블값을 그대로 적용한다.

 

 

이대로 코드를 짜면 문제는 풀린다.

 

근데 dp테이블을 2차원이아니라 1차원으로 푸는 방법이 있다.

이 방식은 1부터 k까지가 아닌 k부터 1까지 내려가며 테이블을 업데이트하는 방식이다.

처음부터 최대로 담을수있는 경우를 고려하면서 업데이트하다보니 1차원배열로도 가능한 것 같다..라고밖에 말을 못하겠다.

DP테이블을 업데이트하는 방식은 거의 동일하다. 다만, 최대무게부터 업데이트하면서 내려오기 때문에 못담는 경우에 대해서는 현상유지자체가 최대값이다. 

담는 경우에선 위와 마찬가지로 담지 않던가, 담은 다음 남는 여유무게만큼의 최대 가치값을 더해주면 된다.

 

 

int dp[100001] = { 0 };
int w[101] = { 0 };
int v[101] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, k;
 
    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 = k; j >= 1; j--)
        {
            if (w[i] <= j) // 담을 수 있으면
            {
                dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
    }
 
    cout << dp[k] << endl;
}

 

수행속도는 약 2.5배?정도 차이가 났다.