현재 가방 번호, 현재 가방에 담긴 보석 무게, 지금까지 담은 보석 목록 메모이제이션 ㄱㄱ
이미 담은 보석이거나, 보석 무게가 가방 무게보다 큰 경우는 탐색하지 않는다. 보석 무게가 가방 무게보단 덜 나가지만 지금 가방에 다른 보석이 들어있어서 보석을 넣을 수 없는 경우는 다음 가방으로 넘긴다. 이 때 마지막 가방을 넘어갔을 경우 -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 푸는 기계가 되는 중.