AcWing 165. 小猫爬山
原题链接
简单
作者:
鳅
,
2023-03-14 20:02:56
,
所有人可见
,
阅读 141
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int res = N;
int cat[N],sum[N];
int n,m;
void dfs(int u,int k)
{
if(k >= res) return;
if(u == n)
{
res = k;
return;
}
for(int i = 0;i < k;i ++)
{
if(cat[u] + sum[i] <= m)
{
sum[i] += cat[u];
dfs(u+1,k);
sum[i] -= cat[u];
}
}
sum[k] = cat[u];
dfs(u+1,k+1);
sum[k] = 0;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n;i ++)
{
cin >> cat[i];
}
sort(cat,cat + n);
reverse(cat,cat+n);
dfs(0,0);
cout << res << endl;
}