题意：
给你n（最大36）个数，让你从这n个数里面找出来一些数，使这些数的和等于s（题目输入），用到的数输出1，没有用到的数输出0
例如：3 4
2 3 4
输出：0 0 1
题解：
认真想一下这一道题，首先看到n不是多大就想用dfs（超时），又在dfs的基础上记忆化（超时），大概是我记忆化不完全。又想用01背包，打出来代码后发现s就是体积，但是s的范围太大了，数组存不下 T_T
看题解发现用一个叫 折半枚举（就是一种思想） 和 二进制枚举 的东西
折半枚举：比如有时集合过大无法全部搜索，但刚好只需要他们的和或其他可以处理出的东西，就可以一半一半搜
知道了这两个东西，你就可以先对输入的n个数据中的前一半枚举，并记录他们每一个状态的值；之后再对后一半枚举，如果在枚举过程中时刻和前一半枚举的数据对照一下，找到了满足题意得方式就跳出循环
代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <string.h> 5 #include<math.h> 6 #include<set> 7 #include<map> 8 using namespace std; 9 const int maxn = 105; 10 const int INF=0x3f3f3f3f; 11 const int mod=1000000007; 12 typedef long long ll; 13 ll n,s,a[maxn],p[maxn]; 14 int main() 15 { 16 map<ll,string>m1; 17 map<ll,string>m2; 18 scanf("%lld%lld",&n,&s); 19 for(ll i=0;i<n;++i) 20 scanf("%lld",&a[i]); 21 for(ll i=0;i<1<<(n/2);i++) 22 { 23 string vis; 24 ll sum=0; 25 for(ll j=0;j<n/2;j++) 26 { 27 if((i>>j)&1) 28 { 29 sum=sum+a[j]; 30 vis.push_back('1'); 31 } 32 else vis.push_back('0'); 33 } 34 m1[sum]=vis; 35 } 36 for(ll i=0;i<1<<(n-n/2);i++) 37 { 38 string vis; 39 ll sum=0; 40 for(ll j=0;j<n-n/2;j++) 41 { 42 if((i>>j)&1) 43 { 44 vis.push_back('1'); 45 sum+=a[n/2+j]; 46 } 47 else vis.push_back('0'); 48 } 49 m2[sum]=vis; 50 if(m1.count(s-sum)) 51 { 52 cout<<m1[s-sum]<<m2[sum]<<endl; 53 break; 54 } 55 } 56 return 0; 57 }
顺便在补充一下位运算：
>> :右移 最高位是0，左边补齐0;最高为是1，左边补齐1
<< :左移 左边最高位丢弃，右边补齐0 （数据没有溢出情况下，右移==除2；左移==乘2）
>>>：无符号右移 无论最高位是0还是1，左边补齐0
2 >> 2 == 4
4 >> 2 ==16
4 << 2 ==1