poj 2923 状态压缩dp

本文主要是介绍poj 2923 状态压缩dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f
int dp[1025];
int vis[1025],w[105],d[1025];
int n,c1,c2;
int judge(int x)
{int sum=0;memset(vis,0,sizeof(vis));vis[0]=1; for(int k=0;k<n;k++){if((1<<k)&x){sum+=w[k];if(sum>c1+c2)return 0;for(int j=c1;j>=w[k];j--)if(vis[j-w[k]])vis[j]=1;}}for(int i=c1;i>=0;i--)if(vis[i]&&sum-i<=c2)return 1;	return 0;	
}
int main()
{int T,tot,t=1;scanf("%d",&T);while(T--){dp[0]=0; scanf("%d%d%d",&n,&c1,&c2);for(int i=0;i<n;i++)scanf("%d",&w[i]);tot=0;for(int i=0;i<(1<<n);i++)if(judge(i))d[tot++]=i;memset(dp,0x3f,sizeof(dp));dp[0]=0; for(int i=0;i<tot;i++){for(int j=((1<<n)-1);j>=0;j--)if(dp[j]!=INF){if(j&d[i])continue;dp[d[i]|j]=MIN(dp[j]+1,dp[d[i]|j]);}} printf("Scenario #%d:\n%d\n\n",t++,dp[(1<<n)-1]);}
}

这篇关于poj 2923 状态压缩dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---