CSES - Shared codeLink to this code:
https://cses.fi/paste/11d967d1f06868a5597cc3/
#include<bits/stdc++.h>
#define inf 1e9+5
#define N 20
#define fr first
#define sc second
using namespace std;
int v[N];
pair <int, int> dp[(1 << N)];
bool comp(pair <int, int> a, pair <int, int> b){
if(a.fr > b.fr) return true;
if(a.fr < b.fr) return false;
if(a.sc > b.sc) return true;
return false;
}
int main(){
int n, x;
cin >> n >> x;
for(int i = 0;i < n;i++){
cin >> v[i];
}
dp[0].fr = 0;
dp[0].sc = 0;
for(int mask = 1;mask < (1 << n);mask++){
dp[mask] = {inf, inf};
for(int i = 0;i < n;i++){
if((mask & (1 << i)) != 0){
int s = (mask ^ (1 << i));
pair <int, int> aux;
if(dp[s].sc + v[i] > x){
aux.fr = dp[s].fr +1;
aux.sc = v[i];
}
else aux = {dp[s].fr, dp[s].sc + v[i]};
if(comp(dp[mask], aux)){
dp[mask] = aux;
}
}
}
// cout <<mask << " " << dp[mask].fr << " " << dp[mask].sc << "\n";
}
cout << dp[(1 << n)-1].fr + (dp[(1 << n) - 1].sc == 0 ? 0 : 1) << "\n";
return 0;
}