[C++] DP - Knapsack Algorithm(가방 문제)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    int n, m, w, v;
    cin >> n >> m;
    vector<int> dy(m+1,0);
    
    for(int i = 0; i < n; i++){
        cin >> w >> v;
        for(int j = w; j <= m; j++){
            dy[j] = max(dy[j], dy[j-w]+v);
        }
    }
    
    cout << dy[m];
    return 0;
}

1. 다이나믹 테이블을 정의한다.

2. 입력 순서대로 dy테이블에 값을 할당한다.

보석3을 넣긴 하지만 넣어도 변하지 않으므로 그대로 두겠다.

보석4를 넣긴 하지만 넣어도 변하지 않으므로 그대로 두겠다

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard