原题传送门
题意
你有 $n$ 个物品和 $m$ 个背包，物品有各自的质量且不可被分割，包也有各自容量。求装完所有物品所需要的最小背包数量。
思路
看到背包和物品，我们很容易想到背包问题，但这道题背包容量太大了，根本开不下这么大的数组。于是我们继续观察数据，发现 $n\le24$，而每个物品都只有放了或没放两种情况，意味着总状态数最大为 $2^{24}=16777216$，那么这就是一个状压 dp 问题了。
既然确定了总方法，我们就来继续分析题目。首先容易发现一个贪心思路：先放满大的背包，再放小的，即需要按照背包容量进行降序排序。
然后就要进行状态转移，为了记录答案，我们首先用 $f_k$ 记录放置 $k$ 中的物品需要用到的背包数量。依照上面的贪心，我们在大的背包没放满前不能开小的背包，所以还需要用一个$g_k$ 表示在当前状态下，剩余容量最大的背包的剩余容量。
接下来思考转移条件。容易发现，对于某个物体，如果当前背包能放下，那么就放进去；如果在目前开的这些背包里剩余容量最大的背包放不下，就必须要新开一个背包，而新开的这个背包如果也放不下，由于我们是降序排序背包容量，则这个物品根本放不下，就不需要更新答案。对于能放下的情况，我们依然要进行进一步判断，由于我们希望背包数量尽可能少且背包剩余容量尽可能多，判断条件也呼之欲出：背包数量变少或者剩余背包最大容量变大的情况可以更新答案。
那么整体思路就有了：先降序排序背包，再依次枚举放哪个物品，依照转移条件更新答案。
这里无解也是很容易判断的。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int a[30],c[110];
int f[16777216],g[16777216];
bool cmp(int x,int y){return x>y;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>c[i];for(int i=1;i<(1<<n);i++)f[i]=111;//初始化，我们这里默认了f[0]=0 sort(c+1,c+m+1,cmp); //降序排序背包容量 for(int i=0;i<(1<<n);i++){ //枚举状态 for(int j=1;j<=n;j++){ //枚举放哪个物品 if(!((i>>(j-1))&1))continue; //这里是因为我们必须保证在状态i下是放了物品j的 int k=i^(1<<(j-1)); //这个式子表示i中去掉j不放的状态 if(g[k]>=a[j]){//如果背包容量足够，不用开新的 if(f[i]>f[k]||f[i]==f[k]&&g[i]<g[k]-a[j]){//背包数量变少或者剩余背包容量变大 f[i]=f[k];//更新答案 g[i]=g[k]-a[j];}}else{//需要开新的背包 if(c[f[k]+1]>=a[j]){//这里是判断新的背包能否放下，如同之前分析，如果新的背包也放不下那么这个物体就放不下了 if(f[i]>f[k]+1||f[i]==f[k]+1&&g[i]<c[f[k]+1]-a[j]){//这里原理与上面一样，不过由于新开了一个背包，所以要加一 f[i]=f[k]+1;//更新答案 g[i]=c[f[k]+1]-a[j];}}}}}if(f[(1<<n)-1]==111)cout<<"NIE";else cout<<f[(1<<n)-1];return 0;
}