[백준 12865번] [동적 계획법] 평범한 배낭

DP를 활용한 문제이다.

 

동적 계획법을 활용한 문제는 메모이제이션(Memoization)을 활용하여 반복되는 계산을 줄이고 완전탐색을 할 것인지 구조를 잡는 것이다.

이 문제에서 i번째 물건까지를 handling하면서 총 V의 부피를 할당했다고 했을 때 max value를 저장해두면

dp[i][j] = dp[i -1, j] 와 dp[i - 1, j - i번째 부피] + i번째 value 중 최댓값을 저장해두면 된다.

(특히 array의 index와 정보를 매칭하는 아이디어는 잘 기억해두도록 하자.)

 

즉, 전후 참조하는 것이 아니라 index가 더 낮은 부분만을 참고하면서 위로 올라가는 형태이므로 DP로 처리하기에 적합하다.

 

단, 이 문제에서 주의할 지점은 가장 Base case에 대한 처리인데

맨 바닥은 이전 index가 존재하지 않고, 또한 할당된 부피 안에 들어갈 수 있으면 그냥 집어넣은 것이 최대이다.

따라서 들어갈 수 있는지를 먼저 체크하고, 들어갈 수 있으면 집어넣으면 된다.

 

위의 내용을 코드로 구현한 결과는 다음과 같다.

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

using namespace std;
#define INF 123456789;

int item_num, max_weight;
int W[1000];
int V[1000];
int dp[1000][100001];

int dp_check(int index, int weight){
    if(weight < 0) return -INF; // BAD cases
    if(index < 0) return 0; // BAD cases
    if(dp[index][weight] != 0) return dp[index][weight]; // 이미 존재하는지 체크(Memoization)
    int current_weight = W[index];
    int current_value  = V[index];
    
    return dp[index][weight] = max(dp_check(index - 1, weight - current_weight) + current_value, dp_check(index - 1, weight));

}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> item_num >> max_weight;

    for(int i = 0;i < item_num; i++){
        int weight, value;
        cin >> weight >> value;
        W[i] = weight;
        V[i] = value;
    }// Data store

    memset(dp, 0, sizeof(dp)); // Initialize 0

    dp_check(item_num - 1, max_weight);
    cout << dp[item_num -1][max_weight] << "\n";

    return 0;
}

이 문제에서 가장 중요한 지점은 dp_check에서 weight의 유효성을 먼저 체크한 것이다.

index가 넘어가는 것은 0으로 취급해주는 것으로 충분하지만, weight가 불가능한 경우는 아애 케이스에서 지워주어야 한다.

따라서 극단적으로 Return value를 -INF처리하여 max함수를 거치면서 걸러지도록 하였다.

 

좀 헷갈리니 여러번 봐두도록 하자.

무난하게 통과하였다.