[Computer Algorithms] DP : Knapsack Algorithm (냅색 알고리즘)

냅색 알고리즘

최대 용량이 K인 가방이 있을 때, 그 가방에 담긴 물건들의 가치의 합이 최대가 되게 하는 알고리즘.

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

int N, K;
vector<int> W, V, dp;

void input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        int w, v;
        cin >> w >> v;
        W.push_back(w);
        V.push_back(v);
    }
}

void solve()
{
    dp.resize(K + 1, 0);

    for (int i = 0; i < N; i++)
    {
        for (int w = K; w - W[i] >= 0; w--)
        {
            dp[w] = max(dp[w], dp[w - W[i]] + V[i]);
        }
    }
}

void output()
{
    cout << dp[K] << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    input();
    solve();
    output();
    return 0;
}

 

1. DP 테이블을 0으로 초기화 한다. (DP[i]는 최대 용량이 i인 가방이 있을 때, 그 가방에 담긴 물건들의 가치의 합이 최댓값을 의미한다.)

2. 입력 한 물건 순서대로 DP 테이블을 갱신해준다. (DP[w]는 현재 DP[w]값과 현재 물건을 제외 했을 때의 값에 현재 물건의 가치를 더한 DP[w - W[i]] + V[i] 중 더 큰 값을 택하도록 한다.)

3. 모든 물건에 대해서 DP 테이블 갱신이 끝나면 DP[K] 값을 통해 가방의 용량이 최대 K 일 때, 그 가방속에 있는 물건들의 가치의 합의 최댓값을 구할 수 있다.