[백준] 12865 평범한 배낭, C++

 

12865번: 평범한 배낭

문제 요약

N개의 물건으로 가방을 싸는 문제
최대 무게 K를 넘지 않으면서 가방에 든 물건이 최대 가치를 지녀야한다.

접근

1. Greedy

무게가 높고 가치가 높은 순으로 정렬한 뒤에 하나씩 넣으면서 해도
정렬을 한뒤에 풀어도 괜찮은지 고민해봤지만 풀리지 않는 예제가 있어서 바로 넘어갔다.

2. Bruteforce

그 다음 쉬운 방법인 브루트 포스 이다.
모든 물건에 대해서 넣거나 넣지 않거나 모두 확인 하면 된다.

#include <iostream>
#include <algorithm> // max
#define MAX_SIZE 100
using namespace std;

int N, K, answer;
int W[MAX_SIZE], V[MAX_SIZE], visit[MAX_SIZE];
void backtrack(int ind, int total_w, int total_v);

int main()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> W[i] >> V[i];
    }
    backtrack(0, 0, 0);
    cout << answer << endl;
    return 0;
}

void backtrack(int ind, int total_w, int total_v)
{
    if (ind == N)
    {
        answer = max(answer, total_v);
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (visit[i]) continue;
        if (total_w + W[i] <= K)
        {
            visit[i] = 1;
            backtrack(ind + 1, total_w + W[i], total_v + V[i]);
            visit[i] = 0;
        }
        backtrack(ind + 1, total_w, total_v);
    }
}

이렇게 하면 O(2^N)이 나오게 되고 이문제에선 N=100 이므로 O(2^100) 이 된다.
2^100 = 1.27e+30 이므로 제한 조건인 2초는 무조건 넘는다.

가지치기(무게를 넘는 것은 더이상 탐색하지 않는 것)를 진행해도 최악의 상황(K=100,000 이고 N=100에 모든 W=1인 경우)은 똑같이 O(2^100)이 된다.

3. Dynamic Programming

사실 메모리 제한(512MB)만 보면 공간복잡도를 포기하고 시간을 취하는 DP로 접근해야할 것이라는 생각이 들 것이다.
하지만 공간복잡도에 어떤 값을 저장을 해야할지 떠오르지 않았고 며칠동안 진전이 없어 관련 알고리즘을 찾았다.

• N개의 집합 A가 n번째 보석을 포함하고 있다면, A에 속한 보석들의 총 가격은 n-1개의 보석들 중에서 최적으로 고른 가격의 합에다가 보석 n의 가격을 더한 것과 같다. (단, n번째 보석을 넣었을 때 배낭이 터지지 않아야 한다)

이 알고리즘에서 다음과 같은 점화식을 뽑아낼수 있다.
P[i, w] = max(v_i + P[i-1, w-w_i], P[i-1, w])
= P[i-1, w]
이걸 다시 풀어보면

1. 현재 무게를 더했을때 최대 무게를 넘기지 않은 경우는 두개 중에 큰값을 저장한다.
   • i 번째 물건을 추가하지 않았을때의 최대 값에 i 번째 물건의 가치를 더한 값
   • i-1 번째까지의 최대 값
2. 현재 무게를 더했을때 최대 무게를 넘기는 경우는 이전값을 저장한다.

그러면 저장하는 배열은 이차원 배열(memo[i][w]) 이 되고
저장하는 값은 최대무게가 w인경우 i 번째 물건 까지의 가치의 최댓값이 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, K, answer;
int memo[101][100001];

int main()
{
    vector<pair<int,int>> item;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        int w, v;
        cin >> w >> v;
        item.push_back({w, v});
    }

    for (size_t i = 1; i < N+1; i++)
    {
        for (size_t w = 1; w < K+1; w++)
        {
            if (item[i-1].first > w)
            {
                memo[i][w] = memo[i-1][w];
            }
            else 
            {
                memo[i][w] = max(
                    memo[i-1][w],
                    memo[i-1][w - item[i-1].first] + item[i-1].second
                );
            }
        }
    }
    answer = memo[N][K];
    cout << answer << endl;
    return 0;
}

4. DP 2

아쉽게 불참한 동아리원's algorithm
같은 DP이긴 한데 Top-Down 방식이다.
Devide&Conquer + Memoization

#include <iostream>
#include <memory.h>
#define max(a, b) (a > b ? a : b)

using namespace std;

int dp[100001][101], item[101][2];
int n, k;

int getAnswer(int weight, int idx) 
{
    if (idx < 0) return 0;    
    if (dp[weight][idx] != -1) return dp[weight][idx];

    dp[weight][idx] = getAnswer(weight, idx - 1);

    if (weight - item[idx][0] >= 0) 
    {
        dp[weight][idx] = max(
            dp[weight][idx],
            getAnswer(weight - item[idx][0], idx - 1) + item[idx][1]
        );
    }

    return dp[weight][idx];
}  

int main()
{
    cin >> n >> k;
    for (int i = 0; i < k + 2; i++) 
        memset(dp[i], -1, sizeof(int) * (n + 1));

    for (int i = 0; i < n; i++) 
        cin >> item[i][0] >> item[i][1];

    cout << getAnswer(k, n - 1);
    return 0;
}

새로 알게된 것

• DP는 TOP DOWN도 되고 BOTTOM UP도 되므로 서로 바꿔보는 연습을 해도 괜찮을듯
  • 점화식이 생각나면 BOTTOM UP으로 하고
  • 생각 안나면 TOP DOWN