도둑질(with 비트마스킹, dp)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, M, C;
int jewel[15]; 
int dp[11][1<<13][21];

 // [현재가방][챙긴보석][남은한도] 
 
int solve(int cur, int visited, int capacity)
{

//기저조건
    if(cur == M)
    {
        return 0;
    }
    
    if(dp[cur][visited][capacity] != 0)
    {
        return dp[cur][visited][capacity];
    } 
    
    for(int i = 0; i < N; i++)
    {

//이미 방문한 적 있을 경우
        if(visited & (1 << i))
        {
            continue;
        }    
        

//capacity가 초과할 경우, cur+1을 통해 새로운 가방에 삽입
        if(capacity < jewel[i])
        {
            dp[cur][visited][capacity] = max(dp[cur][visited][capacity], solve(cur+1, visited, C));    
        }
        else 
        {

//무조건 넣는 게 조건이므로, 넣고 본다. 초과하지 않으면, 해당 보석을 넣고, 1을 더한다. 

//return 까지 가면, 다시 돌아갈 것이다. 이때 보석을 넣었단 의미에서 1을 더한다.
            dp[cur][visited][capacity] = max(dp[cur][visited][capacity], solve(cur, visited | (1 << i), capacity - jewel[i]) + 1);
        }
    } 
    
    return dp[cur][visited][capacity];
}
 
int main(void)
{
    cin >> N >> M >> C;
    
    for(int i = 0; i < N; i++)
    {
        cin >> jewel[i];
    }
    
    cout << solve(0, 0, C);
    
    return 0;
}