1 문제

다이나믹 프로그래밍 문제 중 0-1 배낭 채우기

2 Idea

다이나믹 프로그래밍을 이용해 (N+1)*(K+1) 배열을 만들어 점화식을 이용해 하나씩 채운다

3 Code

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

#include <iostream>
#include <vector>

typedef struct{
    int weight;
    int value;
} thing;

int FindMaxValue(const std::vector<thing>& v, const int N, const int K){
    std::vector<std::vector<int>> dp(K+1, std::vector<int>(N+1, 0));

    for (int j=1; j<=N; ++j){
        for (int i=1; i<=K; ++i){
            if (v[j].weight > i){
                dp[i][j] = dp[i][j-1];
            }
            else{
                if (i-v[j].weight>=0){
                    dp[i][j] = dp[i-v[j].weight][j-1]+v[j].value;
                }                
                dp[i][j] = std::max(dp[i][j-1], dp[i][j]);
            }
        }
    }

    return dp[K][N];
}

int main(){
    int N = 0;
    std::cin >> N;

    int K = 0;
    std::cin >> K;

    std::vector<thing> v;
    v.push_back({0,0});
        //push back garbage
    for (int i=0; i<N; ++i){
        int weight = 0;
        int value = 0;

        std::cin >> weight >> value;

        v.push_back({weight, value});
    }

    std::cout << FindMaxValue(v, N, K) << std::endl;

    return 0;
}

4 Reference

https://jeonyeohun.tistory.com/86