AcWing 165. 小猫爬山
原题链接
简单
作者:
十六
,
2021-01-20 16:00:01
,
所有人可见
,
阅读 263
#include<bits/stdc++.h>
using namespace std;
const int MAX = 20;
int n, w, ans = MAX;
int c[MAX];
int g[MAX];
void dfs(int num, int pos){
if(num>=ans) return;
if(pos==n){
ans = num;
return ;
}
for(int i=0; i<num; i++){
if(g[i]+c[pos]<=w){
g[i] += c[pos];
dfs(num, pos+1);
g[i] -= c[pos];
}
}
g[num] += c[pos];
dfs(num+1, pos+1);
g[num] -= c[pos];
}
int main(){
scanf("%d%d", &n, &w);
for(int i=0; i<n; i++) scanf("%d", &c[i]);
sort(c, c+n, greater<int>());
dfs(1, 0);
cout<< ans<< endl;
return 0;
}