Baekjoon 12865번 평범한 배낭

문제

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

걸린 시간

01 : 59 : 30 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, k;
int volume[101], need[101];
int cache[100001][101];

int pack(int capacity, int item){
    // 메모이제이션
    int& ret = cache[capacity][item];
    if(ret != -1)
        return ret;
    // 재귀 호출
    int ans = 0;
    for(int i = item+1; i <= n; i++)
        if(capacity+volume[i] <= k)
            ans = max(ans, pack(capacity+volume[i], i)+need[i]);
    return ret = ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> volume[i] >> need[i];
    memset(cache, -1, sizeof(cache));
    cout << pack(0, 0) << "\n";
    return 0;
}

이 문제는 배낭 문제(knapsack problem)라고 부르는 조합 최적화의 유명한 문제 중 하나이다.

배낭 문제에는 여러 가지 다른 형태가 있는데 그중 대표적인 각 물건을 최대 하나만 고를 수 있는 0/1 배낭 문제로 완전 탐색에 메모이제이션을 적용하여 쉽게 해결할 수 있다.

하지만 중복이 발생하는 부분을 정확히 찾아내지 못하여 풀지 못했다...