POJ 2923 Relocation 状态DP+01背包

比较综合的题目。
有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);
[cpp] 
#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; 
} 
作者：ACM_cxlove