[12865]평범한 배낭

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

 

배낭 문제는 다이나믹 프로그래밍의 대표적인 문제 중 하나이다. 대학교 알고리즘 수업을 들을 때 풀어봤던 문제라서 풀이 전략을 떠올리는 것은 어렵지 않았으나 세부적인 코드를 짜는데 시간이 조금 걸렸다. 나 같은 경우 2차원 배열의 테이블을 만들어서 풀었는데 이같은 풀이 방법으로 더 간단히 짤 수도 있을거라 본다. 한편 백준에서 다른 사람들이 푼 걸 보면 가끔 말도 안되게 간단하게 풀어서 제출하는 걸 심심찮게 보는데 이 문제도 그렇다.

 

동적 프로그래밍의 '프로그래밍'의 뜻은 우리가 익히 알고 있는 뜻이 아닌 표(테이블)을 의미한다. 몇차원이든 표에 기록하고 그 기록들을 참조해서 문제를 해결해나간다. 문제를 푸는 방식에는 보텀업(bottom up)과 탑다운(top down)방식이 존재하고 보통 보텀업 방식으로 푼다.

 

이 문제의 경우 행의 크기는 물건의 개수, 열의 크기는 최대로 담을 수 있는 총 무게만큼 정해서 만든다. 각 공간에는 그 차수의 물건까지 담았을때 담을 수 있는 물건들의 무게별 최대 '가치'를 저장한다. 가령 1번째 물건의 무게가 3 2번째 물건의 무게가 2일 경우 2행의 2열, 3열, 5열에 해당 무게(물건들의 합)의 최대 가치가 저장된다.

 

#include <iostream>

int table[101][100001];

using namespace std;

int main()
{
    int N = 0, K = 0;
    int weight[101];
    int worth[101];  
    
    cin >> N >> K;
    for(int i = 1; i <= N; i++)
    {
        cin >> weight[i] >> worth[i];
    }
    
    table[1][weight[1]] = worth[1];
    
    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            if(table[i-1][j] > 0)
            {
                if(table[i][j] < table[i-1][j])
                    table[i][j] = table[i-1][j];
                int temp = j + weight[i];
                if(temp <= K)
                {
                    if(table[i-1][temp] < table[i-1][j] + worth[i])
                        table[i][temp] = table[i-1][j] + worth[i];
                }
                    
            }
        }
        if(table[i][weight[i]] < worth[i])
            table[i][weight[i]] = worth[i];

    }
    
    int max = 0;
    for(int i = 1; i <= K; i++)
    {
        if(max < table[N][i])
            max = table[N][i];
    }
    
    cout << max << endl;
}