[알고리즘 풀이 분석] BOJ 12865 평범한 배낭

오늘 풀어본 문제는 BOJ 12865 평범한 배낭 이다!
아니 골드 5래서 패기롭게 도전했건만 와이리 어렵나고,, 자신감 하.락. 😞
DP의 일종인? Knapsack 이라는 알고리즘 이라는데 난 처음 들어본 알고리즘 이었다,,
뭐 굳이 그걸 몰라도 DP 개념으로 풀 수 있지만,, 암튼,, DP를 다양하게 많이 풀어봐야겠다 역시

BOJ 12865 평범한 배낭

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입출력

풀이

이 문제의 접근 개념은 2일 전에 풀었던 BOJ 9084 동전 문제와 유사하다!

이 문제에서도 역시 2차원 dp 배열이 필요하다.
dp[i][j] 에는 가방을 최대 j 무게를 채우려 할 때 0번째 물건부터 i번째 물건까지 중에서 사용되는 물건들의 최대 가치 합이 적혀진다.

물건 1: <6, 13>

첫번째로 무게가 6이고 가치가 3인 물건을 사용해보자.

무게가 6인 물건으로는 5이하의 무게가 최대인 배낭을 채우는 것은 불가능하다. 때문에 무게가 v인 물건이라면 물건이 사용되기 전, 가방의 최대 무게가 v 보다 작을 때는 v를 넣지 않았을 때의 최대 가치, dp 값을 그대로 유지하고 이는 어떠한 물건도 넣지 않았을 때의 가치 0을 유지한다.

• 가방의 최대 무게가 6일 때
  물건 1을 넣으려면 기존의 가방의 무게는 0이다.
  무게가 0인 배낭의 가치는 0, 물건 1의 가치는 13이 더해져 dp[1][6] = 13 이 적힌다.

• 가방의 최대 무게가 7일 때
  물건 1을 넣으려면 기존 가방의 무게는 1이어야 하고 물건 1을 넣지 않고 가방의 무게가 1일 때 가방의 최대 가치는 dp[0][1] = 0 이므로 dp[1][7] = dp[0][1] + 13 이다.

물건 2: <4, 8>

이렇게 dp[1] 한줄을 완성하고 이번엔 무게가 4이고 가치가 8인 물건 2를 넣어보자.

• 가방의 최대 무게가 4일 때
  물건 2를 넣어서 가방을 완성하려면 물건 2를 넣지 않은 가방의 무게가 0이어야 한다!
  이때, dp[2][4] = dp[1][0] + 8 = 8 이고 이 값은 그동안 물건 2를 넣지 않고 가방 무게가 4일때의 최대 가치 값 dp[1][4] = 0 보다 큰 값이기 때문에 dp[2][4] 에는 8이 적힌다.

• 가방의 최대 무게가 6일 때
  물건 2를 넣어서 가방을 완성하려면 물건 2를 넣지 않은 가방의 무게가 2이어야 하고 이 값은 dp[1][2]에 적혀있다!
  물건 2를 넣는다면 가방의 가치는 dp[1][2] + 8 = 8 이지만
  물건 2를 넣지 않는다면 가방의 가치는 dp[1][6] = 13 이므로 더 큰 값이 채택되어 dp[1][6]엔 13이 적히게 된다.

이와 같은 방식으로 dp 배열을 완성하고 모든 아이템을 사용 후보로 두고 최대 무게가 K인 가방의 최대 가치 값 dp[물건 갯수][K] 를 정답으로 반환한다!

코드

#include <iostream>
#include <vector>

// BOJ 12865 평범한 배낭, DP
using namespace std;


int getMaxValue(vector<pair<int, int>> items, int K){
    vector<vector<int>> dp(items.size(), vector<int>(K+1));

    for (int i = 0; i <= K ; ++i) {
        dp[0][i] = 0;
    }

    for (int i = 1; i < items.size(); ++i) {
        // 배낭 전체 무게가 해당 아이템보다 작을 때는 기존의 dp 값 유지
        for (int j = 0; j < items[i].first; ++j) { 
            dp[i][j] = dp[i-1][j];
        }

        // i번째 아이템을 사용할 때와 사용하지 않았을 때 가치의 최댓값으로 dp 완성
        for (int j = items[i].first; j <= K ; ++j) {  
            int left = j - items[i].first;
            dp[i][j] = max(dp[i-1][j], dp[i-1][left] + items[i].second);
        }
    }

    return dp[items.size()-1][K];
}

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

    int N, K;
    cin>>N>>K;
    vector<pair<int, int>> items(N+1, make_pair(0,0));

    for (int i = 1; i <= N; ++i) {
        cin>>items[i].first;
        cin>>items[i].second;
    }

    int value = getMaxValue(items, K);

    cout<<value;

    return 0;
}