acwing165. 小猫爬山

题目

题解

够装就将当前u装入，不够装，就新开一辆车来装

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int n,w,cost[N],sum[N];
int ans=N;

void dfs(int u,int k){
    if(k>=ans)return;
    if(u==n){
        ans=k;
        return;
    }
    for(int i=0;i<k;i++){
        if(sum[i]+cost[u]<=w){
            sum[i]+=cost[u];
            dfs(u+1,k);
            sum[i]-=cost[u];
        }
    }
    sum[k]=cost[u];
    dfs(u+1,k+1);
    sum[k]=0;
    
}
bool cmp(int &a,int &b){
    return a>b;
}
int main(){
    cin>>n>>w;
    for(int i=0;i<n;i++)cin>>cost[i];
    sort(cost,cost+n,cmp);
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}