12865번 평범한 배낭

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

knapsack 알고리즘이다.

#include <bits/stdc++.h>
 
using namespace std;
 
int N, Capacity, dp[101][100001]; // dp[인덱스][용량]
vector<pair<int, int> > items;
 
int knapsack(int pos, int cap)
{
    if (pos == N) return 0;
 
    // cache
    int & ret = dp[pos][cap];
    if (ret != -1) return ret;
 
    // 현재 pos 번째의 가방 무게(first)가 남은 용량(cap)보다 적다면
    if (items[pos].first <= cap) ret = knapsack(pos + 1, cap - items[pos].first) + items[pos].second;
    
    // 현재 가방(pos)을 선택하지 않고, 다음 가방(pos + 1)을 선택할 수 있다.
    ret = max(ret, knapsack(pos + 1, cap));
 
    return ret;
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    memset(dp, -1, sizeof(dp));
    int W, V;
    scanf("%d %d", &N, &Capacity);
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &W, &V);
        items.push_back({ W, V });
    }
 
    printf("%d\n", knapsack(0, Capacity));
 
    return 0;
}