Description

有n个物品，m块钱，给定每个物品的价格，求买物品的方案数。

Solution

敲一道搜索水题吧…

Meet-in-the-Middle思想，分成两部分搜

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           typedef long long LL;using namespace std;int n;LL m,w[45];vector
           
            v[2];void dfs(int x,int y,LL c,int f){ if(x>y) {v[f].push_back(c);return;} if(c+w[x]<=m)dfs(x+1,y,c+w[x],f); dfs(x+1,y,c,f);}int main(){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); dfs(1,n/2,0,0); dfs(n/2+1,n,0,1); sort(v[0].begin(),v[0].end()); sort(v[1].begin(),v[1].end()); int i=0,j=v[1].size()-1; LL ans=0; while(i
            
             =0) { while(v[0][i]+v[1][j]>m&&j>=0)j--; ans+=j+1; i++; } printf("%lld\n",ans); return 0;}