2324: 光头强购买新家具

参考代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,m;

int a[10005];

bool vis[12005];

int cnt[100005];

int main()

{

   while(cin>>n&&n!=0)

   {

       memset(vis,0,sizeof(vis));

       for(int i=0;i<n;i++)

       {

           cin>>a[i];

       }

       sort(a,a+n);

       cin>>m;

       int ans=1;

       cnt[0]=0;

       int maxz=0;

       for(int i=0;i<n;i++)

       {

               int temp=ans;

               for(int j=0;j<temp;j++)

               {

                   int v=cnt[j]+a[i];

                   if(cnt[j]<=m&&!vis[v])

                   {                  

                       cnt[ans++]=v;//

                       vis[v]=1;

                       maxz=max(maxz,v);

                   }

               }

       }

       cout<<m-maxz<<endl;

   }

}