欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

 

上一篇: 双向加密

下一篇: