[백준] 12865 평범한 배낭 - 다이나믹 프로그래밍

[ 문제링크 ]

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

 

🚩 조건

1. 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어짐
2. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어짐
3. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력해라

 

 

🚩 접근

0/1 Knapsack 문제.. 어떻게 푸는 거였더라...

 

 

🚩 시행착오

처음엔 Branch and Bound로 시도해보려 하다가 그래프를 어떻게 정의해야 할지 감이 안와서.. 포기

알고리즘 시간에 배운 기억으로는 DP로 푸는 게 최악의 경우 시간복잡도가 Brute Force와 같아진다고 했는데.. => 이건 N이 엄청나게 커졌을 때! 그래서 Backtracking과 Branch & Bound 라는 새로운 접근법이 대두됨

 

어쨌든 이 문제는 DP로 풀면 된다!

 

 

💻 코드 (C++)

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

int D[101][100001];    // 1-indexed
vector<int> wv;    // 0-indexed
vector<int> vv;    // 0-indexed
int main(){
    int n, k, w, v;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>w>>v;
        wv.push_back(w);
        vv.push_back(v);
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(j-wv[i-1] < 0)
                D[i][j]=D[i-1][j];
            else
                D[i][j]=max(D[i-1][j], D[i-1][j-wv[i-1]]+vv[i-1]);
        }
    }
    cout<<D[n][k];
}