[백준] 12865 평범한 배낭

배낭 알고리즘은 DP의 대표적인 문제라고 한다.

(사실 처음 봄.. ㅎ)

 

문제를 풀고 보니 앞선 문제에서 사용했던 LCS 푸는 방법과 유사했다.

 

예시를 통해서 알아보자 (백준 예제를 살짝 변형한 예제이다)

다음과 같이 입력을 받았다고 하자

index는 arr 배열에서의 index를 의미한다

여기서 weight = 0, value = 1이다. 

ex) arr [1][weight] = 6, arr [1][value] = 13

 

LCS 알고리즘에서 DP table에 값을 저장할 때 해당 값의 유무가 아닌 이전 값을 고려하여 정보를 저장했다.

(먼저 혼자서 끄적여 본 표..)

위 표에서 자세하게 봐야할 부분은 (n=3, k=7)인 부분이다.

arr에서 (n<=3) 이하의 데이터들 중 무게 최대(k)가 7 이하가 되는 방법으로는

무게가 6인 물건 하나 인 경우, 무게가 3, 4인 물건 2개를 고르는 방법이다.

 

따라서 dp[3][7]에는 max(무게가 6인 물건 하나의 가치, 무게가 3, 4인 물건 2개 가치의 합)가 되어야 한다.

이 부분에서 약간 멘붕이 온다.

 

무게가 3, 4인 물건 2개인 가치의 합은 어떻게 구하지..?

 

눈썰미가 좋은 사람들은 빨리 찾을 수 있다..!! (hint: dp [3][7])

 

무게가 3인 물건 = i값 = 3 = arr [3]으로 접근이 가능하므로 

무게가 3인 물건의 가치는 arr [3][1]이 된다.

 

무게가 4인 물건의 가치는 이미 우리가 표의 앞부분에 기록해 두었다.

무게가 4인 물건의 가치 = dp [2][4]

dp [2][4]를 일반화하면 dp [i-1][ j - arr [i][weight]]이다.

만약 dp [i][j - arr [i][weight]]인 경우

dp [2][8]을 계산할 때 무게가 4인 물건이 2번 들어가게 된다. 

따라서 해당 행이 아닌 이전 행을 사용해야 한다.

 

□ 소스코드

#define WEIGHT 0
#define VALUE 1

void normalBag12865(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n,k;
    cin>>n>>k;

    int arr[n+1][2];
    int dp[n+1][k+1];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            dp[i][j] = 0;
    

    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        arr[i][WEIGHT] = a;
        arr[i][VALUE] = b;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(j - arr[i][WEIGHT] >= 0){
                dp[i][j] = max(dp[i-1][j-arr[i][WEIGHT]] + arr[i][VALUE], dp[i-1][j]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout<<dp[n][k]<<endl;
}

 

너무 어려워 ㅜㅜ