[NOIP2001]装箱问题 dfs超时的看这里

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int v,n,kkk[35];
int a[35];
bool vis[35];
void dfs(int x,int y){
    if(y>=kkk[x]){
        return;
    }
    if(y<0||x>n){
        return;
    }
    kkk[x]=min(kkk[x],y);
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(x+1,y-a[i]);
            vis[i]=0;
        }
    }
}
int main(){
    for(int i=0;i<35;i++){
        kkk[i]=20005;
    }
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(0,v);
    int kk=20005;
    for(int i=0;i<35;i++){
        kk=min(kk,kkk[i]);
    }
    cout<<kk<<endl;
    return 0;
}