[Gold Ⅴ] 평범한 배낭 - 12865

[문제 위치]

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

[문제 풀이]

재귀적으로 푸는 문제이다.

각 물건은 담는다, 안 담는다로 구분되며 이 둘 중 더 큰 가치를 만드는 선택을 취해야 한다.

따라서 go(pos, sum)를 이용해 pos번째 물건부터의 선택을 재귀적으로 분기하며, 기저 조건(pos==n 등)에 도달할 때까지 내려가 계산한다.

다만 서로 다른 선택 경로가 같은 상태(pos, sum)에 도달할 수 있어 같은 계산이 반복되므로, go(pos, sum)의 결과를 d[pos][sum]에 저장해두는 메모이제이션을 사용한다.

즉, 앞으로 볼 물건과 남은 용량을 고려하는 것이다.

아래는 이를 구현한 코드이다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int d[111][111111];
int w[111], v[111];
int n, k;
int go(int pos, int sum) {
    if (sum < 0 ) return -987654321;
    if (sum == 0 || pos==n) return 0;
    int&ret = d[pos][sum];
    if (ret != -1) return ret;
    ret = 0;
    return ret = max(go(pos + 1, sum - w[pos]) + v[pos], go(pos + 1, sum));
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf(" %d %d", &w[i], &v[i]);
    printf("%d\n", go(0, k));
}