对于一个集合,他一有2^n个子集,而状态压缩就是枚举这些子集,每一个状态就是一个由01构成的集合,如果为0就表示不选当前的元素,否则就表示选。因为状态压缩将每一个状态压缩成了一个用二进制表示的数,所以不光可以节省空间,还可以节省时间。因为是枚举子集,所以时间复杂度为O(2^n)),一般使用的标志就是n≤20代码:#include using namespace std;#define endl '\n'#define int long longsigned main(){ios::sync_with_stdio(false);cin.tie(0); int n,w; cin>>n>>w; vector cnt(14); for(int i=1;i { int x; cin>>x; cnt[x]++;}vector sum(1vector dp(1 //初始化for(int i=1;i{for(int j=0;j{if(i>>j&1) sum[i]+=cnt[j+1];}}dp[0]=0;for(int i=1;i{for(int j=i;j;j=(j-1)&i) //dp转移 该状态是从前一个状态转移而来 0101 从0001或0100转移{if(sum[j]>w) continue;elsedp[i]=min(dp[i],dp[i-j]+1);}}coutreturn 0;}#许愿池#