12865번 평범한 배낭

문제 링크

평범한 배낭

문제 풀이

가방에 물건을 넣을건지 말건지 결정하는 문제이다. 함수 solve(n, k)는 남은 용량 k에 대해 n번째 물건에서부터 마지막 물건까지 넣으면서 얻을 수 있는 최대 가치를 의미한다. 물건을 넣었을 때 남은 용량이 0 이하가 되어 가방이 버틸 수 없는 경우와 마지막 물건까지 다 본 경우를 기저 사례로 둔다.

구현

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

const int INF = 987654321;

int N, K, W[101], V[101];
int cache[101][100001];

int solve(int n, int k) {
    if (k < 0) return -INF;
    if (n == N) return 0;

    int& ret = cache[n][k];
    if (ret != -1) return ret;
    ret = solve(n + 1, k - W[n]) + V[n];
    ret = max(ret, solve(n + 1, k));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    for (int i = 0; i < N; ++i)
        cin >> W[i] >> V[i];
    memset(cache, -1, sizeof(cache));

    cout << solve(0, K);
    return 0;
}