对于一个集合,他一有2^n个子集,而状态压缩就是枚举这些子集,每一个状态就是一个由01构成的集合,如果为0就表示不选当前的元素,否则就表示选。因为状态压缩将每一个状态压缩成了一个用二进制表示的数,所以不光可以节省空间,还可以节省时间。因为是枚举子集,所以时间复杂度为O(2^n)),一般使用的标志就是n≤20代码:#include <bits/stdc++.h>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<int> cnt(14);for(int i=1;i<=n;i++){int x;cin>>x;cnt[x]++;}vector<int> sum(1<<13);vector<int> dp(1<<13,14);//初始化for(int i=1;i<(1<<13);i++) //枚举2的13次方的状态{for(int j=0;j<13;j++) //每个状态代表的值{if(i>>j&amp;1) sum[i]+=cnt[j+1];}}dp[0]=0;for(int i=1;i<(1<<13);i++) //枚举每个状态{for(int j=i;j;j=(j-1)&amp;i) //dp转移 该状态是从前一个状态转移而来 0101 从0001或0100转移{if(sum[j]>w) continue;elsedp[i]=min(dp[i],dp[i-j]+1);}}cout<<dp[(1<<13)-1]<<endl;return 0;}