Relocation POJ - 2923(状态压缩+2次01背包+好题,强烈推荐)
程序员文章站
2024-03-14 13:46:34
...
题意:一个人要搬家 ,有两个车,有n件物品,现在问至少搬多少次就能将所有东西搬完?
题解:刚开始想的是是不是要先01背包装小车,再01背包装大车,发现有很大的局限性,最后看了题解简要,一气呵成,这应该是个老题,不过论质量绝对经典,这其中运用了状态压缩,首先考虑的是把所有能一次运走的物品组合看成一个状态,也就是看成一个新的物品,在算这个是否能一次运走可以使用01背包中的装满背包的写法,然后此时就打出了所有体积的组合,最后枚举下,看是否能一次运走,有了状态后,也就是有了这些新物品后,就可以再次01背包了,只不过这次部分物品之间有冲突,肯定啊,你这不能运走了再拿回来,再运,这样肯定是耽搁事的,之后01背包的写法大大改下,这就感觉像是不断的枚举了。
附上代码:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1500;
const int inf=0x3f3f3f3f;
int tot,state[maxn];
int dp[maxn];
int n,v1,v2;
int c[maxn];
bool vis[maxn];
bool ok(int x)
{
int sum=0;
memset(vis,0,sizeof(vis));
vis[0]=1;
for(int i=0;i<n;i++){
if((x>>i)&1){
sum+=c[i];
for(int j=v1;j>=c[i];j--){
if(vis[j-c[i]]){
vis[j]=1;
}
}
}
}
if(sum>v1+v2){
return 0;
}
for(int i=0;i<=v1;i++){
if(vis[i]&&sum-i<=v2){
return 1;
}
}
return 0;
}
void init()
{
tot=0;
for(int i=1;i<(1<<n);i++){
dp[i]=inf;
if(ok(i)){
state[tot++]=i;
}
}
}
int main()
{
int T;
scanf("%d",&T);
int casen=1;
while(T--){
scanf("%d%d%d",&n,&v1,&v2);
for(int i=0;i<n;i++){
scanf("%d",&c[i]);
}
init();
int V=(1<<n)-1;
dp[0]=0;
for(int i=0;i<tot;i++){
for(int j=V;j>=0;j--){
if(dp[j]==inf){
continue;
}
if((j&state[i])==0){
dp[j|state[i]]=min(dp[j|state[i]],dp[j]+1);
}
}
}
printf("Scenario #%d:\n%d\n",casen++,dp[V]);
if(T){
puts("");
}
}
return 0;
}
上一篇: 双向加密