题解 P5997 【[PA2014]Pakowanie】
Kiloio
·
·
题解
状压DP
第一眼看上去像背包，然而不是的。
首先基础贪心策略：
为了包数最少，肯定是尽量先用大包的。
状态：
$g[i]$表示所有已用背包（即为$i$集合中表示已经用了的）中剩下的**最大空间**
$g$存的是剩下的**最大空间**，这样就能满足**上述贪心策略**。
### 方程：
直接看代码里的方程（**代码中有解释**）吧($i$是集合，$j$是枚举的子集)：
```
if(i&(1<<(j-1))){//如果j在子集里，没在就不管他
op=i^(1<<(j-1));
//两种情况，每种情况中还会有两种情况
if(g[op]>=a[j]){//当前物品，不用再开一个包就能装下 。即剩余最大空间满足j物品的大小。
//如果下一个背包大于或等于（等于还需一个条件，另一条件解释在下），更新。
if(f[i]>f[op] || (f[op]==f[i] && g[op]-a[j]>g[i])){//等于情况还加了比较新包装后剩余空间，为合并后的结果（其实也是两种情况），也可以分开写
f[i]=f[op];
g[i]=g[op]-a[j];
}
}
//剩余空间不够，需要再开一个包（ b记录的是包的空间）
else if(b[f[op]+1]>=a[j]){//下一个包也要装得下，如果下一个包还装不下就放弃
//这里道理跟上面一样
if(f[i]>f[op]+1 || (f[op]+1==f[i] && b[f[op]+1]-a[j]>g[i])){
f[i]=f[op]+1;
g[i]=b[f[op]+1]-a[j];
}
}
}
```
### 没了。完整代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<25)+5;
int n,m,a[110],b[110],f[N],g[N],maxn;
bool cmp(long long x,long long y){
return x>y;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
for(int i=1; i<=m; i++){
scanf("%d",&b[i]);
}
maxn=(1<<n)-1;
sort(b+1,b+1+m,cmp);
for(int i=1; i<=maxn; i++){
f[i]=m+1;
}
int op;
for(int i=0; i<=maxn; i++){
for(int j=1; j<=n; j++){
if(i&(1<<(j-1))){
op=i^(1<<(j-1));
if(g[op]>=a[j]){
if(f[i]>f[op] || (f[op]==f[i] && g[op]-a[j]>g[i])){
f[i]=f[op];
g[i]=g[op]-a[j];
}
}
else if(b[f[op]+1]>=a[j]){
if(f[i]>f[op]+1 || (f[op]+1==f[i] && b[f[op]+1]-a[j]>g[i])){
f[i]=f[op]+1;
g[i]=b[f[op]+1]-a[j];
}
}
}
}
}
if(f[maxn]>=m+1){
cout<<"NIE";
return 0;
}
cout<<f[maxn];
}
```