题目描述

blablabla

dfs

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 20;
int n,m;
int w[N]; 
int s[N];
int ans = N;

void dfs(int u,int cnt){   // u代表当前是第几只猫  cnt代表缆车数
    if(cnt > ans) return ; //剪枝
    if(u == n){
        ans = cnt;
        return ;
    }
    for(int i = 0; i < cnt; i ++){
        if(s[i] + w[u] <= m){
            s[i] += w[u];
            dfs(u + 1,cnt);
            s[i] -= w[u];
        }
    }
    s[cnt] = w[u];   //当当前的缆车都放不下时，购买新的缆车，并将u放入新缆车里
    dfs(u + 1,cnt + 1);
    s[cnt] = 0;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++) scanf("%d",&w[i]);
    sort(w,w + n);
    reverse(w,w + n); // 降序排序 目的也是为了加快速度
    dfs(0,0);

    cout << ans << endl;
    return 0;
}