BOJ - 12865 평범한 배낭

12865번 평범한 배낭

DP 문제 중 knapsack(배낭 문제)에 해당하는 문제이다.

정해진 무게에 대하여 해당 무게를 넘지 않으면서 가치를 최대한 누리기 위한 문제로, 모든 경우에 대해 브루트 포스를 통해 구한다면 굉장히 많은 반복 횟수를 가져야 한다는 단점이 있다.

또한 greedy 알고리즘의 경우 주어진 물건을 나눌 수 있을 때는 효과적이지만(Fractional knapsack 일 때)
이번 문제의 경우 물건을 온전히 가져가느냐 마냐의 문제이기 때문에 greedy는 적절하지 못한 방법이다.

따라서 DP를 통해 문제를 해결 할 수 있다.

가장 주 된 아이디어는 다음과 같다.

1. 물건을 선택함에 있어서 해당 물건이 가져갈 수 있는 무게보다 더 크다면 선택이 불가능하다.
2. 물건을 선택하지 않았을 때의 기대값(가치)과 물건을 선택했을 때의 기대값을 비교하여 전자가 더 크다면 선택을 안하고, 후자가 더 크다면 선택을 한다.

정리해 보자면 주어진 물건의 개수를 N, 가져갈 수 있는 최대 무게를 W라 하고 i번째 물건의 무게를 wi, i번째 물건의 가치를 pi라 하자.

그리고 n번째 물건 까지 누적된 최대 기대값을 P(n, ww)로 나타낸다고 하자.
(ww는 가져갈 수 있는 무게)

위의 표현식으로 만약 i번째 물건에 대하여 i번째 물건을 선택하지 않았을 경우의 기대값은 선택하기 전 최대 기대값인 P(i-1, ww) 가 되고, i번 째 물건을 선택했을 때의 기대값은 P(i-1, ww - wi) + pi가 된다.

따라서 두 값 중 큰 값을 골라 가며 누적해 가는 것이고 이러한 방식은 DP를 통해 풀 수 있는 것이다.

코드

#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,k;
    cin >> n >> k;

    int *W = new int[n+1];
    int *V = new int[n+1];

    for(int i=1;i<=n;i++)
    {
        cin >> W[i] >> V[i];
    }

    int **arr = new int*[n+1];
    for(int i=0;i<n+1;i++)
    {
        arr[i] = new int[k+1];
    }

    for(int i=0;i<=k;i++)
        arr[0][i] = 0;

    for(int i=1;i<=n;i++)
    {
        arr[i][0] = 0;
        for(int j=1;j<=k;j++)
        {
            if(W[i] > j) // 무게가 담을 수 있는 공간보다 클 때
                arr[i][j] = arr[i-1][j];
            else
            {
            /** i번째 물건을 선택하지 않았을 때와 선택했을 때 크기 비교 **/
                if(arr[i-1][j] > arr[i-1][j-W[i]] + V[i])
                    arr[i][j] = arr[i-1][j];
                else
                    arr[i][j] = arr[i-1][j-W[i]] + V[i];
            }
        }
    }
    cout << arr[n][k];

    return 0;
}

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