状压dp

对于一个集合，他一有2^n个子集，而状态压缩就是枚举这些子集，每一个状态就是一个由01构成的集合，如果为0就表示不选当前的元素，否则就表示选。因为状态压缩将每一个状态压缩成了一个用二进制表示的数，所以不光可以节省空间，还可以节省时间。
因为是枚举子集，所以时间复杂度为O(2^n)),一般使用的标志就是n≤20

代码:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
signed 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;
else
dp[i]=min(dp[i],dp[i-j]+1);
}
}

cout<<dp[(1<<13)-1]<<endl;
return 0;
}#许愿池#