평범한 배낭 문제

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

12865번: 평범한 배낭

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

#include <iostream>
#include <stdio.h>

#define max_size 101

using namespace std;

int main(){
    int n, k;
    int w[max_size], v[max_size];
    
    int dp[max_size][100001];

    cin >> n >>k;

    for(int i=1; i<n+1; i++){
        cin >> w[i] >> v[i];
    }

    for(int i=1; i<n+1; i++){
        for(int j=1; j<k+1; j++){
            if( j-w[i]>=0){
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }

    cout <<dp[n][k];
    return 0;
}