[백준] 12865 | 평범한 배낭 | C++

풀이의 출처: https://chanhuiseok.github.io/posts/improve-6/

이 문제는 냅색 알고리즘(knapsack algorithm)이 무엇인지 알 수 있게 해주는 문제이다.

풀이의 핵심은 2가지로 나눠서 볼 수 있다.

 

1. 이차원 다이나믹 테이블 풀이

 

준비물이 있다.

i번째 물건의 무게를 저장하는 배열 W,

i번째 물건의 가치를 저장하는 배열 V,

i번째 물건까지 고려할 때 j용량까지 담을수 있는 최대가치값 dp[][]

 

dp[i][j]의 의미는

i번째 물건까지 고려할 때, j용량에 담을 수 있는 가치값의 최대합이다.

따라서 다음과 같이 2중 for문을 작성하려 한다.

1번째 물건부터 n번째 물건까지 i반복:
    1용량부터 k용량까지 j반복:
    
    	j번째 용량에 i물건 투입가능:
        	dp[i][j] 작성 = (???)
            
        j번째 용량에 i물건 투입불가능:
        	dp[i][j] 작성 = dp[i-1][j];

 

 

i번째 물건을 넣을 수 있다고 할 때,

다음과 같은 선택사항이 있을 것이다.

 

1. 넣을 것인가?

2. 넣지 않을 것인가?

 

먼저 넣는다고 하면,

이전 물건까지 고려했을 때 용량이 j-W[i]까지 허락한 상태에서

i번째 물건의 가치인 V[i]를 더해주면 된다.

dp[i-1][j-W[i]]+V[i];

 

넣지 않겠다면,

이전 물건까지 고려했을 때 용량이 j인 상태 그대로를 담아주면 된다.

dp[i-1][j];

 

우리는 이제 이 두 값중 더 큰 값을 넣어주면 된다.

1번째 물건부터 n번째 물건까지 i반복:
    1용량부터 k용량까지 j반복:

        j번째 용량에 i물건 투입가능:
            dp[i][j] 작성 = max(dp[i-1][j-W[i]]+V[i], dp[i-1][j]);
            
        j번째 용량에 i물건 투입불가능:
            dp[i][j] 작성 = dp[i-1][j];

 

정답 소스코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    int W[104], V[104];
    cin>>n>>k;
    vector<vector<int> > dp(n+1, vector<int>(k+1, 0));
    for(int i=1; i<=n; i++) cin>>W[i]>>V[i];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=k; j++) {
            if(j>=W[i]) dp[i][j]=max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][k];
    return 0;
}

 

놀랍게도, dp 테이블을 1차원으로 작성할 수도 있다.

 

---

 

2. 일차원 다이나믹 테이블 풀이

 

준비물이 있다.

i번째 물건의 무게를 저장하는 배열 W,

i번째 물건의 가치를 저장하는 배열 V,

j용량까지 담을 수 있는 최대가치값 dp[]

 

이전과 많이 비슷하지만 약간의 차이가 있다.

dp[j]값은 j용량까지 담을 수 있는 가치의 최대합이다.

그리고 dp값은 0으로 초기화되어있다.

 

의사코드를 보자

1번째 물건부터 n번째 물건까지 i반복:
    k용량부터 1용량까지 j반복:

        j번째 용량에 i물건 투입가능:
            dp[j] 작성 = max(dp[j], dp[j-W[i]]+V[i]);

 

dp는 한 줄짜리 배열이다.

이제 1부터 i번째 물건까지 차례로 고려해 나갈때마다

dp는 한 줄이 통째로 갱신될 것이다.

 

정답 소스코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    int W[104], V[104];
    cin>>n>>k;
    vector<int> dp(k+1);
    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(j>=W[i]) dp[j]=max(dp[j], dp[j-W[i]]+V[i]);
        }
    }
    cout<<dp[k];
    return 0;
}

 

---

 

필자의 포스트는

설명보다는 '기록'에 목적을 두었다.

더 자세한 설명은 맨 위의 링크를 참고바란다.