自动搬运

查看原文

来自洛谷，原作者为

	Kiloio QAQ

搬运于2025-08-24 22:16:20，当前版本为作者最后更新于2021-01-13 13:00:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

状压DP

第一眼看上去像背包，然而不是的。

首先基础贪心策略：

为了包数最少，肯定是尽量先用大包的。

状态：

$f[i]$表示前$i$个物品用的个数，用的二进制表示（毕竟是状压）

$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];
}