보석 모으기

백준 1480번: 보석 모으기

아이디어

현재 가방 번호, 현재 가방에 담긴 보석 무게, 지금까지 담은 보석 목록 메모이제이션 ㄱㄱ

이미 담은 보석이거나, 보석 무게가 가방 무게보다 큰 경우는 탐색하지 않는다. 보석 무게가 가방 무게보단 덜 나가지만 지금 가방에 다른 보석이 들어있어서 보석을 넣을 수 없는 경우는 다음 가방으로 넘긴다. 이 때 마지막 가방을 넘어갔을 경우 -1을 반환해서 숫자를 맞춰주는게 포인트.

코드

#include <bits/stdc++.h>

using namespace std;

int N, M, C; // gem, bag, limit
int arr[13];
int cache[11][21][1<<13]; // bag, weight, visited

int solve(int bag, int weight, int visited) {
    if (bag == M) return -1;
    if (visited == (1<<N)-1) return 0;

    int& ret = cache[bag][weight][visited];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < N; i++) {
        if (visited&(1<<i)) continue;
        else if (arr[i] > C) continue;
        else if (weight+arr[i] > C) {
            ret = max(ret, solve(bag+1, arr[i], visited|(1<<i))+1);
        }
        else {
            ret = max(ret, solve(bag, weight+arr[i], visited|(1<<i))+1);
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> C;
    for (int i = 0 ; i < N; i++) {
        cin >> arr[i];
    }
    memset(cache, -1, sizeof(cache));
    cout << solve(0, 0, 0);
    return 0;
}

여담

비트마스킹 DP 푸는 기계가 되는 중.