[c++] 백준 12865 - 평범한 배낭(동적 계획법, 이후 다시 풀어보자)

0. [c++] 백준

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

1. 풀이

이 문제를 풀기 위해서 처음에 입력을 받은 후, 오름차순으로 정렬을 하고, 메모이제이션을 활용해서 문제를 해결해보았다.

하지만, 그러한 풀이가 기초적인 풀이보다 계산시간이 느리기에 단순한 반복문을 활용해서 문제를 풀게 되었다.

나중에 메모이제이션을 제대로 활용해서 다시 풀어보자.

이 반복문에서 특이한 부분이 있는데, j가 K부터 1까지 감소하는 형태로 반복을 하는 것이다.

이는 오름차순으로 반복을 하게 될 경우 Arr[i].first의 크기마다 중첩해서 더해지기 때문에 이러한 방법을 활용하였다.

ex. cache[0] = k, 

cache[0 + Arr[i].first] = k + Arr[i].second,

cache[0 + 2 * Arr[i].first] = k + 2 * Arr[i].second,

...

cache[0 + N * Arr[i].first] = k + N * Arr[i].second

따라서 이러한 중첩을 막기 위해서 가장 마지막 부분부터 더해주는 것이다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include<iostream> #include<algorithm> #include<vector>   using namespace std;   typedef unsigned long long ull;   int N, K; vector<pair<int, int> > Arr; int cache[100001];   void dp() {     for (int i = 0; i < N; i++) {         for (int j = K; j >= 1; j--) {             if (Arr[i].first <= j) {                 cache[j] = max(cache[j], cache[j - Arr[i].first] + Arr[i].second);             }         }     }       cout << cache[K]; }     int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       //W = 무게, V = 가치     int W, V;     int ret = 0;       cin >> N >> K;       for (int i = 0; i < N; i++) {         cin >> W >> V;         Arr.push_back({ W,V });     }          dp();       return 0; } Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!