记录编号	571839	评测结果	ATTTTTTTTT
题目名称	送礼物	最终得分	10
用户昵称	䱖虁職	是否通过	未通过
代码语言	C++	运行时间	36.000 s
提交时间	2022-06-25 14:51:44	内存使用	5.16 MiB

#include<bits/stdc++.h>
using namespace std;
int w,n,g[50],vis[50]={0},best=0;
int dfs(int sum)
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            if(sum+g[i]<=w)
            {
                vis[i]=1;
                best=max(best,sum+g[i]);
                if(best==w)return 0;
                dfs(sum+g[i]);
                vis[i]=0;
            }
        }
    }
    return 0;
}
int main(){
    freopen("giftgiving.in","r",stdin);
    freopen("giftgiving.out","w",stdout);
    scanf("%d%d",&w,&n);
    for(int i=1;i<=n;i++)scanf("%d",&g[i]);
    dfs(0);
    printf("%d\n",best);
    return 0;
}