[Algorithm/BOJ] 12865.평범한 배낭 C++ : DP, Knapsack Problem

배낭 문제 즉, Knapsack Problem은 물건의 갯수와 배낭의 최대 용량, 각 아이템의 무게와 가치를 입력받고 최대 가치를 구하는 문제이다.

이는 DP, 백트래킹, Branch and Bound 등등... 풀 수 있는 방법이 굉장히 다양한데 이번에는 DP로 접근하는 방식에 대해 다뤄보려고 한다. 

 

DP는 부분 문제를 바탕으로 결과값을 도출하는 방식이다...

DP 자체에 대한 글은 나중에 다뤄보도록 하고 아무래도 혼자 점화식을 구상하는 능력이 매우매우 떨어지는 것 같고 이번에도 다른 분의 글을 바탕으로 이해하며 코드를 작성해보았다.

배낭의 무게를 임시로 설정해서 각 무게에 해당할 때 마다 최대 가치를 저장하는 부분이 중요하다고 생각했다...

 

#include <iostream>

using namespace std;

int N, K, W[101], V[101], dp[101][100001];


int main(){
    cin>> N >> K;
    for(int i=1; i<=N; i++){
        cin >> W[i] >> V[i];
    }

    for(int i=0; i<K; i++){
        dp[0][i] = 0;
    }
    for(int i=0; i<N; i++){
        dp[i][0] = 0;
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=K; j++){
            if(W[i]>j) dp[i][j] = dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]);
        }
    }

    cout << dp[N][K] << '\n';

}

 

 

참고!

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C-Knapsack-Problem