题意:
两辆车去运一堆货物,货物数量小于等于10,问最少需要几趟能把货物全部运到目的地。
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 const int Ni = 1<<10;
5 const int INF = 1<<27;
6 int dp[Ni],g[Ni],weg[11];
7 bool vis[Ni];
8 int n,c1,c2,s;
9 bool judge(int x)//可以一次用两辆车运走返回true
10 {
11 int i,j,sum=0;
12 for(i=0;i<=c1;i++) vis[i]=0;
13 vis[0]=1;
14 for(i=0;i<n;i++) if(x&(1<<i))
15 {
16 sum+=weg[i];
17 for(j=c1-weg[i];j>=0;j--)//j可以用c1一次运走j+weg[i]就可以一次运走
18 if(vis[j]) vis[j+weg[i]]=1;
19 }
20 for(i=c1;i>=0;i--)//x这个状态可以用两辆车一次运完return true
21 if(vis[i]&&sum-i<=c2) return true;
22 return false;
23 }
24 int main()
25 {
26 int i,j,t,cs=1;
27 cin>>t;
28 while(t--)
29 {
30 scanf("%d%d%d",&n,&c1,&c2);
31 for(i=0;i<n;i++) scanf("%d",weg+i);
32 if(c1>c2) swap(c1,c2);
33 for(s=0,i=1;i<1<<n;i++)//找出可以一次运走的所有状态
34 if(judge(i)) g[s++]=i;
35 for(i=(1<<n)-1;i>0;i--) dp[i]=INF;
36 dp[0]=0;
37 for(i=0;i<s;i++)
38 for(j=(1<<n)-1-g[i];j>=0;j--)//因为g[i]可以一次运走
39 if(!(j&g[i])) dp[j|g[i]]=min(dp[j|g[i]],dp[j]+1);
40 printf("Scenario #%d:\n%d\n\n",cs++,dp[(1<<n)-1]);
41 }
42 return 0;
43 }