[백준 12865] 평범한 배낭 (DP) (C/C++) (★)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, K;
int dp[101][100001];
int w[101];
int v[101];
 
int solve(int item, int capacity)
{
    if(item >= N)
    {
        return 0;
    }
    
    if(dp[item][capacity] != 0)
    {
        return dp[item][capacity];
    }
    
    // 배낭에 넣지 않는 경우 
    dp[item][capacity] = solve(item+1, capacity);     
    
    // 배낭에 넣는 경우 
    if(capacity-w[item] >= 0)
    {
        dp[item][capacity] = max(dp[item][capacity], solve(item+1, capacity-w[item]) + v[item]);    
    } 
    
    return dp[item][capacity]; 
}
 
int main(void)
{
//    freopen("B12865_input.txt", "r", stdin);
    
    cin >> N >> K;
    
    for(int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];    
    }
    
    cout << solve(0, K);
    
    return 0;
}