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

装货物-状压dp

程序员文章站 2024-03-23 22:53:58
...

传送门:装货物

要想到状压是求出了所有状态以及每一种状态的不同产生情况,保留每个状态最优的产生情况。

代码:

#include<bits/stdc++.h>
using namespace std;
int w[30];
int dp[2][(1<<21)],p[30];
int main(){
    p[0]=1;
    for(int i=1;i<=22;++i){
        p[i]=p[i-1]*2;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int n,x,W;
        scanf("%d%d%d",&n,&x,&W);
        int Max=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&w[i]);
            Max=max(w[i],Max);
        }
        if(Max>W) {
            puts("No");
            continue;
        }
        memset(dp[0],0x3f,sizeof dp[0]);
       //for(int i=0;i<=(1<<n)-1;++i) dp[1][i]=W;
        dp[0][0]=0;dp[1][0]=0;
        for(int i=0;i<=((1<<n)-1);++i){
            for(int j=0;j<=n-1;++j){
                if(i&p[j]){
                   continue;
                }
                if(w[j+1]<=dp[1][i]){
                    if(dp[0][i]<dp[0][i+p[j]]){
                        dp[0][i+p[j]]=dp[0][i];
                        dp[1][i+p[j]]=dp[1][i]-w[j+1];
                    }
                    if(dp[0][i]==dp[0][i+p[j]]){
                        dp[1][i+p[j]]=max(dp[1][i]-w[j+1],dp[1][i+p[j]]);
                    }
                }
                else {
                    if(dp[0][i]+1<dp[0][i+p[j]]){
                        dp[0][i+p[j]]=dp[0][i]+1;
                        dp[1][i+p[j]]=W-w[j+1];
                    }
                    if(dp[0][i]+1==dp[0][i+p[j]]){
                        dp[1][i+p[j]]=max(W-w[j+1],dp[1][i+p[j]]);
                    }
                }
            }
        }
        if(dp[0][(1<<n)-1]<=x) puts("Yes");
        else puts("No");
    }
 
    return 0;
}
相关标签: 状态压缩