状压DP 小W选书籍

#include<bits/stdc++.h>
using namespace std;
int f[1<<23],v[1<<23];
int n,m;
int a[100010];
inline int read(){
     int x=0,f=1;
     char ch=getchar();
     while(ch<‘0‘||ch>‘9‘){
         if(ch==‘-‘)
             f=-1;
         ch=getchar();
     }
     while(ch>=‘0‘&&ch<=‘9‘){
         x=(x<<1)+(x<<3)+(ch^48);
         ch=getchar();
     }
     return x*f;
}

inline void write(int x){
     char F[200];
     int tmp=x>0?x:-x ;
     if(x<0)putchar(‘-‘) ;
     int cnt=0 ;
        while(tmp>0)
        {
            F[cnt++]=tmp%10+‘0‘;
            tmp/=10;
        }
        while(cnt>0)putchar(F[--cnt]) ;
}
main()
{
    //f[i]表示当前状态下的需要用的最小次数
    //v[i]表示当前状态下的需要装的最小体积 
    memset(f,63,sizeof(f));//最后次数要最小，所以初始最大 
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        f[1<<i-1]=1;//初始化 刚开始放任意一个值都为 1 
        v[1<<i-1]=a[i];//最开始容量为取得任意一个值 
    }
    for(int i=1;i<=(1<<n)-1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i&1<<j-1)//若当前的j被取了则进行转移 
            {
                if(v[i^1<<j-1]+a[j]<=m)
                //上一个体积加上当前的体积小于等于总体积 
                {
                    if(f[i^1<<j-1]<f[i])
                    //若上一个最小次数比总共次数小，那么可行 
                    {
                         f[i]=f[i^1<<j-1];//更新 
                         v[i]=v[i^1<<j-1]+a[j];//体积也更新 
                    }
                    if(f[i^1<<j-1]==f[i])
                    {
                        //若次数与总和相等 
                        v[i]=min(v[i],v[i^1<<j-1]+a[j]);
                        //则体积取越小越好 
                        //这样可以保证剩余容量很大，则次数就小 
                    }
                }
                else //上一个体积加上当前的体积大于总体积 
                {
                    if(f[i^1<<j-1]+1<f[i])
                    {
                     
                        f[i]=f[i^1<<j-1]+1;//就要再来一组，装上当前体积
                        v[i]=a[j];
                        //当前状态的体积也要更新
                        //相当于开了一个背包来装另一个    
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1];//枚举完所有状态求其最小次数 
    return 0;
}