POJ 2923 Relocation 状态DP+01背包

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

比较综合的题目。

有n个物品，有两辆车载重分别是c1,c2.问需要多少趟能把物品运完。

n比较小，只有10，而且需要把所有物品全部运完，便想到状态压缩来保存状态。

首先记录好所有的可行状态，对于状态state能一趟运完。

然后再利用01背包，dp[j]，表示已运的状态为j，如果状态j与ok[i]不冲突，则可以从状态j运一趟变为j|ok[i]。

dp[j|ok[i]]=min(dp[j|ok[i]],dp[j]+1);

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-6
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1<<30
using namespace std;
int n,c1,c2,cnt,w[10];
int ok[1<<10];    //能一次装过去的可行状态
int dp[1<<10]; 
bool judge(int state){    //判断state状态的物品能否一次运走
	int sum=0;
	int f[105];
	memset(f,0,sizeof(f));
	f[0]=1;
	for(int i=0;i<n;i++)
		if((1<<i)&state){
			sum+=w[i];     
			for(int j=c1;j>=w[i];j--)    //01背包判断可行否
				f[j]=max(f[j-w[i]],f[j]);
		}	
	if(sum>c1+c2)    //如果总重量超过了两个车之和
		return false;
	for(int i=0;i<=c1;i++)   //如果i可放c1,另外 一部分可以放入c2,则可行
		if(f[i]&&sum-i<=c2)
			return true;
	return false;
}
int main(){
	int t,cas=0;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&c1,&c2);
		for(int i=0;i<n;i++)
			scanf("%d",&w[i]);
		cnt=0;
		for(int i=0;i<(1<<n);i++){
			dp[i]=inf;
			if(judge(i))
				ok[cnt++]=i;
		}
		dp[0]=0;
		for(int i=0;i<cnt;i++)
			for(int j=0;j<(1<<n);j++)
				if(!(ok[i]&j))    //如果两个状态没有冲突
					dp[j|ok[i]]=min(dp[j|ok[i]],dp[j]+1);    //在j的基础上再加入状态ok[i]
		printf("Scenario #%d:\n%d\n\n",++cas,dp[(1<<n)-1]);
	}
	return 0;
}