백준 12865 평범한 배낭

역시 DP 접근 문제이다. 처음 접근은 2*물건의 수 DP 배열을 만들어 물건마다 넣고빼고를 적어두고 다음 물건을 볼 때 두 조건 중 max값을 사용하면 되지 않을까? 싶었는데 머리로 몇번 돌려보니 너무나도 쉽게 전체 탐색이 안되는구나... 하며 고민했다.

 

DP 배열은 물건의 수*가방의 무게 크기로 생성한다. DP[i][j] 는, i 번째 물건까지 사용했을때, j무게 가방에 넣을 수 있는 물건 최대 가치이다. 처음 행은 당연히 첫번째 물건을 넣는 경우이고, 한번 값이 들어가기만 한다.

이후로는 모든 물건을 순회(현재 물건 무게 : curWeight, 현재 물건 가치 : curValue)하면서 DP를 채우게 된다. 매 물건마다 가방 크기를 1씩 늘리면서,

1. 현재 가방 크기가 현재 물건을 넣을 수 있으면
   1. 저번 물건(i - 1), 현재것 가능한 상황(j - curWeight) 에 curValue를 더한 값과
   2. 저번 물건(i - 1), 현재것 안넣은 상황(j) 중 max 값을 현재 DP에 채운다
2. 현재 가방 크기가 현재 물건을 넣을 수 없으면
   1. 저번 물건(i - 1), 현재것 안넣은 상황(j)를 현재 DP에 채운다.

이렇게 전부 넣고 난 뒤, 마지막 값이 모든 물건을 가방에 넣은 최고 value 값이다.

---

#include <iostream>
#include <vector>

struct good{
    int weight;
    int value;
    good(int wIn, int vIn) : weight(wIn), value(vIn) {}
};

// std::ostream& operator<< (std::ostream &os, std::vector<good> goodList)
// {
//     for (int i = 0; i < goodList.size(); i++)
//     {
//         os << goodList[i].weight << " " << goodList[i].value << '\n';
//     }
//     return os;
// }

// struct cmpValue{
//     bool operator() (good g1, good g2)
//     {
//         return g1.value > g2.value;
//     }
// };

// struct cmpWeight{
//     bool operator() (good g1, good g2)
//     {
//         return g1.weight > g2.weight;
//     }
// };

int main()
{
    int N, K;
    std::vector<good> goodList;

    std::cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        int wIn, vIn;
        std::cin >> wIn >> vIn;
        goodList.push_back(good(wIn, vIn));
    }
    std::vector<std::vector<int> > dp(N + 1, std::vector<int>(K + 1, 0));

    for (int i = 1; i <= N; ++i)
    {
        int curWeight = goodList[i - 1].weight;
        int curValue = goodList[i - 1].value;

        for (int j = 1; j <= K; ++j)
        {
            if (j < curWeight)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = std::max(dp[i - 1][j - curWeight] + curValue, dp[i - 1][j]);
        }
    }
    std::cout << dp[N][K];
    // std::cout << goodList;
}

DP 접근의 국룰이라고 하는 0-1 Knapsack 문제 유형이라고 한다. 풀고나서 보니 옛날에 알분때 봤던 기억이 조금 난다. 그때도 진짜 머리 뽀개지면서 봤었는데 이번에도 그런 것 같다. DP적 사고방식이 아직은 잘 접근하기 어려운것 같다. 계속 문제를 풀어봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.