BOJ 백준 12865 : 평범한 배낭

시작하면서

　이번 문제는 Dynamic Programming 중 배낭 알고리즘(Knapsack Algorithm) 문제이다.

BOJ 12865 - 평범한 배낭

​

문제 이해

​ 이 문제는 배낭 알고리즘이라는 정해진 틀에서 해결하는 문제이다. 다음 링크에서 설명이 잘 되어 있으니 참고 바란다.

​

LINK

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<int>> knapsack;
    vector<int> weight, value;
    int N, K;

    cin >> N >> K;

    weight.resize(N + 1);
    value.resize(N + 1);
    knapsack.resize(N + 1);
    
    for (int i = 1; i <= N; i++)
    {
        cin >> weight[i] >> value[i];
    }

    knapsack[0].resize(K + 1);
    for (int i = 1; i <= N; i++)
    {
        knapsack[i].resize(K + 1);
        for (int j = 0; j <= K; j++)
        {
            knapsack[i][j] = knapsack[i - 1][j];

            if (j - weight[i] >= 0)
            {
                int compareValue = knapsack[i - 1][j - weight[i]] + value[i];
                knapsack[i][j] = max(knapsack[i][j], compareValue);
            }
        }
    }

    cout << knapsack[N][K];

    return 0;
}