题目描述

blablabla

样例

#include<bits/stdc++.h>
using namespace std;
int n,m;
int g;
vector<int>q;
int h[19];
void dfs(int p,int k)
{
    if(p>=g){
        return;
    }
    if(k==n+1){
        g=min(p,g);
        return;
    }
    if(k==1){
        h[1]+=q[k-1];
        dfs(p,k+1);
    }else{
        for(int i=1;i<=p;i++){
            if(h[i]+q[k-1]<=m){
                h[i]+=q[k-1];
                dfs(p,k+1);
                h[i]-=q[k-1];
            }
        }
        if(h[p+1]+q[k-1]<=m){
            h[p+1]+=q[k-1];
            dfs(p+1,k+1);
            h[p+1]-=q[k-1];
        }
    }
}
int main()
{
    cin>>n>>m;
    g=n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        q.push_back(t);
    }
    sort(q.begin(),q.end(),greater<>());
    dfs(1,1);
    cout<<g;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla