蓝桥杯算法训练VIP-装箱问题-题解（C++代码）dfs记忆化搜索

#include <iostream> 
using namespace std;
int v,n;
int a[40];
int vis[40];
int flag;
int maxn=-100;
void dfs(int x,int sum)
{
    if(sum>v) return;
    if(sum==v){
        flag=1;
        return;
    } 
    if(sum<v){
        if(sum>maxn) maxn=sum;
    } 
    if(x>n) return;
    for(int i=x;i<n;i++)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            dfs(i+1,sum+a[i]);
            vis[i]=0;
        }
    }
}
int main()
{
    cin>>v;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    dfs(0,0);
    if(flag==1) cout<<0;
    else cout<<v-maxn;
    return 0;
}