[백준 12865][dp] 배낭: knapsack

드디어 기대하고 기대하던 배낭문제다. 이 문제를 만나고 나서야 DP의 의미를 이해할 수 있게 되었다. 
DP는 a, b, c, d가 있을 때 abc, abd, acd ... 이런 조합을 만드는 문제가 아니었다.

a를 넣었을 때와 넣지 않았을 때 두 개로 나뉜 경우에 대해 각각이 b를 넣었을 때와 넣지 않았을 때로 나누는 방식으로 풀었어야 했다. 헐랭~ 

https://youtu.be/rhda6lR5kyQ?si=wVKtxIhe4A9wsj81

DP는 초깃값 설정이 중요하다. 우리가 구하고자 하는 값은 가치의 최댓값이고, 입력값은 항목의 개수와 각 항목당 무게와 가치가 주어진다. dp의 data는 value 의 sum이다. 가질 수 있는 value의 최대값을 구하는 문제이므로 n 번째 항목까지의 value sum을 확인하는 dp[n][m]을 만든다. 

• 여기서 n은 n번째 index를 가진 항목까지 확인했다는 의미고, m은 들어갈 수 있는 weight을 나타낸다. 

결론을 먼저 말하면 (두괄식) dp[n][m]이 답이 된다. 
dp[n][m]의 max는 n번째 값 weight를 넣었을 때와 넣지 않았을 때를 비교하여 결정한다. 근데 막 넣을 수 있는 게 아니라 weight의 maximum이 있다.

• m(들어갈 수 있는 weight)에서 i의 weight를 뺐을 경우 양수면
  dp[i][j] = max ( dp[ i - 1 ] [ j ] , dp[ i - 1 ][ j - w ] + value[ i ] )
  방금전까지의 최댓값인 dp[i-1][m] 과  지금 weight을 더해서 value가 최대가 되는 경우 중에서 더 큰 값을 고른다.   
• 음수면 dp[i][j] = dp[ i-1 ][j]  

여기서 dp[i-1]이 고정인 이유는 앞서 말했듯이 i번째까지 보는 봤을 때의 최댓값이기 때문에, 현재값은 i - 1 값에 변화가 있거나 없거나의 경우라서 그렇다. (이게 헷갈렸다..)

 

위 예제로 보겠다. 지금 4개의 항목이 들어왔고 무게의 최대는 7이다.
각 항목당 [ index: 1 ] [ weight ] ; value 로 표현해보겠다. Bottom-up 방식으로 풀 것이다. 

weight | index	[0]	[1][6] ; 13	[2][4] ; 8	[3][3] ; 6	[4][5] ; 12
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	13	13	13	13
7	0	13	13	14	14

 

1. 초기값을 설정한다. 
2. weight 5에서 index[4]일 때 변화가 생겼다. 기존값은 index[2] 하나가 들어가 value 8이 최대였다. [4]까지 보면 weight 5를 넘지 않으면서 value는 가장 크기 때문에 12로 바뀐거다. 
3. weight 7 행에서 13 -> 14로 바뀌는 부분을 보면, weight[1] = 6이 7보다 작은 값들 중에 가장 큰 value를 가졌다.
[3]에서 weight 7 - 3 (weight[3])  =  4이고, 이 때 weight[2] = 4를 만족하기에 value는 8+6=14가 된다. 

따지고 보면 weight에 해당하는 행만 보고 있다. 굳이 table을 가지지 않아도 행으로 최대 value를 계산할 수 있다. 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int n, k, w[101], v[101];
    int dp[101][100001] = { 0 };

    cin >> n >> k;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 0; 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;
}

*처음에 런타임 에러가 나서 코드 수정하다가 for (int j = 0) 부분에서 int j = 1 -> 0 수정해서 무게가 같은 경우도 포함해줬다. 

DP가 익숙해지면 메모리에서 재귀 호출이 어떻게 할당되고 해제되는지 CS적으로 이해하는 것도 필요하다. 이를 위해 메모리 관련한 OS의 내용을 정리해서 올려야겠다. 올릴 시간이 되겠찌?.. (할 일 +1)