[1480] 보석 모으기

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

1480번: 보석 모으기

<문제>

탑다운 형식의 냅색을 구현한다고 생각하면 편하다. 물론 일반적인 냅색과 다른점이 몇개 존재하는데,

 

배낭이 여러개 존재 -> 배낭 하나를 subproblem으로 생각, 하나의 depth당 하나의 subproblem을 해결

하나의 depth당 보석에대해 bool[N], 곧 13개의 bool형이 존재 -> (1<<13)<INT_MAX이므로 int로 표현가능

depth가 m일때에는 모든 가방을 채운 경우이므로 check의 비트1이 존재하는 개수만큼 return해주고

그렇지 않을때에는 모든 보석에 대해서 가져가는 경우를 (완전)탐색하면 된다.

하나의 탐색이 끝났다면 하나의 subproblem이 해결되었다고 생각할 수 있고, m개의 subproblem을 해결하기 위해

탐색이 종료된 후에야 depth+1을 재귀호출하는 식으로 구현할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, c, a[14], dp[11][1 << 13][21];
int f(int depth, int check, int cap) {
    if (depth == m) {
        int temp = check;
        int ret = 0;
        while (temp > 0) {
            ret += (temp & 1);
            temp >>= 1;
        }
        return ret;
    }
    if (dp[depth][check][cap] != -1) return dp[depth][check][cap];
    dp[depth][check][cap] = 0;
    int i;
    for (i = 0; i < n; i++) {
        if ((1 << i) & check) continue;
        if (a[i] + cap <= c) {
            int next = check | (1 << i);
            dp[depth][check][cap] =
                max(f(depth, next, cap + a[i]), dp[depth][check][cap]);
        }
    }
    return dp[depth][check][cap] =
               max(f(depth + 1, check, 0), dp[depth][check][cap]);
}
int main(void) {
    cin >> n >> m >> c;
    for (int i = 0; i < n; i++) cin >> a[i];
    memset(dp, -1, sizeof(dp));
    cout << f(0, 0, 0);
    return 0;
}