题意：有n件物品，每件容量为wi，有容量分别为c1,c2的两辆车，问最少要几次才能将这些物品运完； 思路：先用状态压缩将一次能运走的物体压缩成一个状态，将问题转换成01背包；
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int n,c1,c2; bool vis[1<<11]; int dp[1<<11]; int cnt; int num[1<<11]; int s[15]; int ok(int sta) { int t=0; memset(vis,false,sizeof(vis)); vis[0]=true; for(int i=0;i<n;i++) { if((1<<i)&sta) { t+=s[i]; if(t>c1+c2) return 0; for(int j=c1;j>=s[i];j--) { if(vis[j-s[i]]) vis[j]=1; } } } for(int i=0;i<=c1;i++) if(t-i<=c2&&vis[i]) return 1; return 0; } int main() { int t; int ca=1; scanf("%d",&t); while(t--) { cnt=0; scanf("%d%d%d",&n,&c1,&c2); for(int i=0;i<n;i++) scanf("%d",&s[i]); int sta=(1<<n)-1; for(int i=1;i<=sta;i++) { if(ok(i)) num[cnt++]=i; } memset(dp,INF,sizeof(dp)); dp[0]=0; for(int i=0;i<cnt;i++) for(int j=sta;j>=0;j--) { if(j&num[i]) continue; if(dp[j]!=INF) { dp[j|num[i]]=min(dp[j|num[i]],dp[j]+1); } } printf("Scenario #%d:\n%d\n\n",ca++,dp[sta]); } }