题意：有n个(n<=10)物品，两辆车，装载量为c1和c2，每次两辆车可以运一些物品，一起走。但每辆车物品的总重量不能超过该车的容量。问最少要几次运完。
思路：由于n较小，可以用状态压缩来求解。
家具从左到右依次对应二进制形式的低位到高位，该位上为1表示该家具还没运走，0表示已经运走。
建立两个数组，s1[],s2[]，分别存储一次性能被货车1和货车2运走的状态。
之后再把s1,s2数组中的状态合并一下，存入到s数组中去，即表示能一次性被两辆货车同时运走的状态。
合并条件：若(s1&s2)=0，即没有重合的，则两者可以合并
dp[i]表示剩余家具状态为i时最少要搬几次
状态转移方程：
dp[j]=min(dp[j-s[i])+1; //当然(s[i]|j)=0，即s[i]为j的子序列
有两个要注意的地方！！！
1.先用vis数组，若vis[s1|s2]=1表示该状态（s1与s2合并的状态）可以一次性被两辆车运走，
之后再把相应的状态存入s1s2数组。
因为如果直接存储，可能会有几次（s1|s2）数值相同的情况，这样可能在s1s2中存储多个相同的值，这样会对答案有影响。
2.一开始忽略一点，就是有可能运家具只是用其中一辆货车，另一辆装不下任何货物。。。
所以状态要从0开始枚举，而不是从1开始。。。
附上两个代码：
01背包，即直接dp方程求解：
#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; const int maxn=(1<<10)+5; int n,c1,c2; int w[11]; //s1存储能一次性被货车1运走的状态，s2存储能一次性被货车2运走的状态，s存储能一次性被两辆货车同时运走的状态 int s1[maxn],s2[maxn],s[maxn]; int vis[maxn]; //标记哪些状态可以一次性被两辆货车运走 int idx1,idx2,idx; int dp[maxn]; void init(){ idx1=idx2=idx=-1; int sum; //忽略一点，就是有可能之后运家具只是用其中一辆货车，另一辆装不下任何货物。。。 //所以状态要从0开始。。。 for(int i=0;i<(1<<n);i++){ sum=0; for(int j=0;j<n;j++){ if(i&(1<<j)){ sum+=w[j]; } } if(sum<=c1) s1[++idx1]=i; if(sum<=c2) s2[++idx2]=i; } /* 先用vis数组存储哪些能一次性运走，之后在存入s数组. 因为如果直接存入s数组的话，可能有好几组s1[i]|s2[j]相同，这样同一个数会存好几次，可能会有影响 */ memset(vis,0,sizeof(vis)); for(int i=0;i<=idx1;i++){ for(int j=0;j<=idx2;j++){ if((s1[i]&s2[j])==0){ vis[s1[i]|s2[j]]=1; } } } for(int i=0;i<(1<<n);i++) dp[i]=INF; for(int i=1;i<(1<<n);i++){ if(vis[i]){ s[++idx]=i; dp[i]=1; } } } int main() { int t; scanf("%d",&t); for(int q=1;q<=t;q++){ scanf("%d%d%d",&n,&c1,&c2); for(int i=0;i<n;i++){ scanf("%d",&w[i]); } init(); for(int i=0;i<=idx;i++){ for(int j=(1<<n)-1;j>=s[i];j--){ if((s[i]|j)==j){ dp[j]=min(dp[j],dp[j-s[i]]+1); } } } printf("Scenario #%d: ",q); printf("%d ",dp[(1<<n)-1]); } return 0; }
dfs记忆化搜索：
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; int s1[2500];//存储可以被c1货车一次性搬走的家具的不同状态，二进制下1代表还没搬，0代表已搬走了 int s2[2500];//存储可以被c2货车一次性搬走的家具的不同状态，二进制下1代表还没搬，0代表已搬走了 int s1s2[2500];//存储可以一次性被两辆车运载的情况 int vis[2500];//vis[i]:若i能一次性被两辆车运走，则vis[i]=1; int index1,index2,index3; int dp[(1<<10)+5];//dp[i]表示剩余家具状态为i时最少要搬几次 int t,n,c1,c2,load; int w[15]; int ans; void init(){ for(int i=0;i<(1<<n);i++){ load=0; //忘记每次开始的时候load=0了； for(int p=0;p<n;p++){ if(i&(1<<p)){ load+=w[p]; } } if(load<=c1){ s1[index1]=i; index1++; } if(load<=c2){ s2[index2]=i; index2++; } } } int dfs(int s){ int ss1,ss2; int ss; if(dp[s]!=-1) return dp[s]; for(int i=0;i<index3;i++){ if(s1s2[i]==s){ dp[s]=1; return dp[s]; } } dp[s]=10000000; for(int i=0;i<index3;i++){ ss=s1s2[i]; if((ss|s)==s){ dp[s]=min(dp[s],dfs(s-ss)+1); } } return dp[s]; } int main() { scanf("%d",&t); for(int i=1;i<=t;i++){ memset(dp,-1,sizeof(dp)); memset(vis,0,sizeof(vis)); index1=index2=index3=0; scanf("%d%d%d",&n,&c1,&c2); for(int j=0;j<n;j++) scanf("%d",&w[j]); init(); int s11,s22; //先将可以一次性被两辆车运走的情况给存起来 for(int m=0;m<index1;m++){ for(int j=0;j<index2;j++){ s11=s1[m]; s22=s2[j]; if((s11&s22)==0){ vis[s11|s22]=1; } } } for(int m=0;m<(1<<n);m++){ if(vis[m]==1){ s1s2[index3]=m; index3++; } } ans=dfs((1<<n)-1); printf("Scenario #%d: ",i); printf("%d ",ans); } return 0; }