백준 No.12865 [평범한 배낭]

Baekjoon Online Judge No.12865 [평범한 배낭]

---

   Problem   

12865번: 평범한 배낭

---

   Code   

#include <iostream>
#include <vector>
#define weight first
#define value second
 
using namespace std;
 
int N, K;
vector<pair<int, int>> loads;
vector<vector<int>> dp;
 
int solve() {
    for (int w = 1; w <= K; w++)
        dp[1][w] = loads[1].weight > w ? 0 : loads[1].value;
 
    for (int i = 2; i <= N; i++)
        for (int w = 1; w <= K; w++)
            if (loads[i].weight > w) dp[i][w] = dp[i - 1][w];
            else dp[i][w] = max(dp[i - 1][w]
                    , dp[i - 1][w - loads[i].weight] + loads[i].value);
 
    return dp[N][K];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> K;
    loads.resize(N + 1);
    dp.assign(N + 1, vector<int>(K + 1, 0));
 
    for (int i = 1; i <= N; i++)
        cin >> loads[i].weight >> loads[i].value;
 
    cout << solve();
}

---

   How to solve   

• dp[ i ][ w ] : 1번째 짐부터 i 번째 짐 까지만 고려하고 최대 들고갈 수 있는 무게가 w 일때 배낭에 넣을 수 있는 가치의 최대값

 #13 ~ #14 line 

  i 의 값이 1일 경우엔, 챙길 수 있는 짐이 loads[1]밖에 없는 것 이므로 위 그림처럼 w 가 loads[1]의 무게 이상이 되었을 경우부터 챙길 수 있게 되고, dp[1][ w ] == loads[1]의 가치 가 된다. 그 이전까진 당연히 아무것도 챙길 수 없으므로 dp[1][ w ] == 0 ( w < loads[1] ) 이 된다. #13 ~ #14 line 에서 이 경우에 대해 처리를 한다.

 

 #16 ~ #20 line 

  loads[ i ]의 무게가 w 이하냐, w 보다 초과냐로 나뉜다.

  loads[ i ]의 무게 > w 이면 이 짐 하나 챙기는 것도 못 하므로 이 짐은 무시된다. 따라서 이 짐은 있으나 마나 이므로 이 짐이 없을때의 dp값이 이 경우의 dp값이 된다. 위 그림의 주황색 테두리 안에 있는 dp[ i ][ w ] 들이 이에 해당한다. 주황색 칸과 화살표를 통해서 직관적으로 나타내 보았다.

• ∴ if loads[ i ].weight > w, dp[ i ][ w ] = dp[ i - 1 ][ w ]

  loads[ i ]의 무게 ≤ w 이면 이 짐을 챙기냐 마냐 결정해야한다. loads[ i ]를 챙기지 않았을 경우의 최대의 가치값인 dp[ i - 1 ][ w ]와 loads[ i ]를 챙기기 위해 loads[1] ~ loads[ i - 1 ] 에서 챙긴 짐들중 loads[ i ]의 무게만큼 짐을 덜었을 때의 가치의 최대값인 dp[ i - 1 ][ w - loads[ i ]의 무게 ] 에 loads[ i ]의 무게를 더한값 중 더 큰 값이 dp[ i ][ w ]가 된다. 설명에 쳐진 음영의 색이 위 그림의 동일한 색의 칸을 나타낸다.

• ∴ if loads[ i ].weight ≤ w, dp[ i ][ w ] = max( dp[ i - 1 ][ w ], dp[ i - 1 ][ w - loads[ i ].weight ] + loads[ i ].value )

 

  dp[ i ][ w ]의 값을 구할 때 참고되는 값은 이미 입력된 input 값 (loads)과 위 그림 기준 이전줄 ( i - 1 ) 의 몇몇개의 값 이므로 탐색 순서는 위 코드처럼 좌에서 우로, 그리고 위에서 아래로 하던지 위에서 아래로, 그리고 좌에서 우로 하던지 상관 없을 것 같다.

 

  그렇게 이전값을 참고해 가며 dp[ i ][ w ]값을 구해가다가 나오는 마지막 값인 dp[ N ][ K ] 의 값이 문제에서 요구하는 해답이 된다.