Relocation POJ-2923

题目意思: 有 n 个货物，并且知道了每个货物的重量，每次用载重量分别为c1,c2的火车装载，问最少需要运送多少次可以将货物运完。
分析：本题可以用二进制枚举所有不冲突的方案，再来dp 一下,一开始dp数组初始化为正无穷,dp[0]=0,代表什么都不运送需要多少趟,对于每个不冲突的选择方案；假设有 5 个物品, 就是更新 dp 数组 00000~11111 的状态的趟数。每次需要用不冲突的方案来更新 dp 数组，如果不冲突的方案与上一个状态不冲突就可以转，值为上一个状态的值+1。
如果值小则更新值，最后 dp [11111] 就是最终答案

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define Max (1<<15)
 6 using namespace std;
 7 const int inf=0x3f3f3f3f;
 8 int s[11],dp[Max],s1[Max],s2[Max],dis[Max];
 9 int main (void)
10 {
11     int t,n,c1,c2,i,j,k,l1,l2,L,cas=1;
12     scanf("%d",&t);
13     while(t--&&scanf("%d%d%d",&n,&c1,&c2))
14     {
15         for(i=0; i<n; i++)
16             scanf("%d",&s[i]);
17         l1=l2=0;
18         for(i=0; i<(1<<n); i++)
19         {
20             k=0;
21             for(j=0; j<n; j++)
22                 if(i&(1<<j))
23                     k+=s[j];
24             if(k<=c1)s1[l1++]=i;
25             if(k<=c2)s2[l2++]=i;
26         }
27         L=0;
28         for(i=0; i<l1; i++)
29             for(j=0; j<l2; j++)
30                 if((s1[i]&s2[j])==0)
31                     dis[L++]=(s1[i]|s2[j]);
32         memset(dp,inf,sizeof(dp));
33         dp[0]=0;
34         for(int i=0; i<L; i++) //????????????.
35             for(int j=0;j<(1<<n); j++)
36             {
37                 if(j&dis[i]||dp[j]==inf) continue;
38                 dp[j|dis[i]]=min(dp[j|dis[i]],dp[j]+1);
39             }
40         printf("Scenario #%d:
%d

",cas++,dp[(1<<n)-1]);
41     }
42     return 0;
43 }