[BOJ 12865번/C++] 평범한 배낭

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

평범한 배낭

문제

문제

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

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

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

 

제한사항

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

풀이

 

최초 풀이(오답)

이전 무게(i)에 현재 물건의 무게(w)를 합한 값이 K보다 작거나 같을 경우 물건을 담는다는 방식으로 다음 점화식을 만들었다.

 

dp[i + w] = max(dp[i + w], dp[i] + v)

 

#include <iostream>
#include <vector>

using namespace std;

int dp[100001];

int main() {
    int N;
    int K;

    cin >> N >> K;

    vector<vector<int>> WV(N + 1, vector<int>(2, 0));

    for (int i = 1; i <= N; i++) {
        cin >> WV[i][0] >> WV[i][1];
        dp[WV[i][0]] = WV[i][1];
    }

    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (i + WV[j][0] <= K) {
                dp[i + WV[j][0]] = max(dp[i + WV[j][0]], dp[i] + WV[j][1]);
            }
        }
    }

    cout << dp[K] << endl;

    return 0;
}

얼핏보면 될 것 같았지만, 이 풀이에는 맹점이 있었다. 같은 짐을 여러개 넣을 수 있다는 점이었다.

 

테스트로 쓴 반례

10 999
46 306
60 311
33 724
18 342
57 431
49 288
12 686
89 389
82 889
16 289

answer : 4655

 

그래서 넣는 짐을 체크해주는 과정도 필요하겠구나~ 해서 코드를 조금 더 추가했다.

 

 

2차 풀이(오답)

이번에는 현재 무슨 짐(j)을 넣는지를 dp배열에서 체크해줘 이전의 짐을 넣은 가방의 가중치와 더했다.

dp[i + w][j] = max(dp[i + w][j - 1], dp[i][j - 1] + v)

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int dp[100001][101];

int main() {
    int N;
    int K;

    cin >> N >> K;

    vector<vector<int>> WV(N + 1, vector<int>(2, 0));

    for (int i = 1; i <= N; i++) {
        cin >> WV[i][0] >> WV[i][1];
        dp[WV[i][0]][1] = WV[i][1];
    }

    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (i + WV[j][0] <= K) {
                dp[i + WV[j][0]][j] = max(dp[i + WV[j][0]][j - 1], dp[i][j - 1] + WV[j][1]);
            }
        }
    }

    cout << dp[K][N] << endl;

    return 0;
}

 

물론 이 방법을 써도 마찬가지였다. 같은 짐이 여러번 들어갈 수 있다는 점은 변하지 않았다.

 

테스트로 쓴 반례

3 5
4 2
3 4
1 5

answer : 9

 

2번의 오답을 겪고 나서야, 검색을 통해 이 문제는 유명한 DP 문제 중 하나인 0-1 Knapsack 문제였다는 것을 알게 되었다.

 

[참고] 자세한 정보는 여기에...

감사합니다...

 

현재 가방에 든 무게(i)와 현재 가방에 넣을지 고민중인 물건의 무게(w), 가중치(v)가 있을 때,

 

dp[i][j] = dp[i][j - 1] (if i < w)

dp[i][j] = max(dp[i][j - 1], dp[i - w][j - 1] + v) (otherwise)

 

라는 점화식이 나온다.

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int dp[100001][101];

int main() {
    int N;
    int K;

    cin >> N >> K;

    vector<vector<int>> WV(N + 1, vector<int>(2, 0));

    for (int i = 1; i <= N; i++) {
        cin >> WV[i][0] >> WV[i][1];
        dp[WV[i][0]][1] = WV[i][1];
    }

    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (i >= WV[j][0]) {
                dp[i][j] = max(dp[i][j - 1], dp[i - WV[j][0]][j - 1] + WV[j][1]);
            }
            else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    cout << dp[K][N] << endl;

    return 0;
}

 

알고리즘 공부가 덜 되어있음을 다시 한 번 느꼈다.

문제를 풀면서 알고리즘을 더 익혀두어야겠다..