Relocation POJ - 2923(状态压缩+2次01背包+好题，强烈推荐)

传送门

题意：一个人要搬家 ，有两个车，有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%dn",casen++,dp[V]);
        if(T){
            puts("");
        }
    }
    return 0;
}

最后

以上就是贪玩月亮为你收集整理的Relocation POJ - 2923(状态压缩+2次01背包+好题，强烈推荐)的全部内容，希望文章能够帮你解决Relocation POJ - 2923(状态压缩+2次01背包+好题，强烈推荐)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。