题意：有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=(<<)+;
int n,c1,c2;
int w[];
//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=-;
int sum;
//忽略一点，就是有可能之后运家具只是用其中一辆货车，另一辆装不下任何货物。。。
//所以状态要从0开始。。。
for(int i=;i<(<<n);i++){
sum=;
for(int j=;j<n;j++){
if(i&(<<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,,sizeof(vis));
for(int i=;i<=idx1;i++){
for(int j=;j<=idx2;j++){
if((s1[i]&s2[j])==){
vis[s1[i]|s2[j]]=;
}
}
}
for(int i=;i<(<<n);i++)
dp[i]=INF;
for(int i=;i<(<<n);i++){
if(vis[i]){
s[++idx]=i;
dp[i]=;
}
}
}
int main()
{
int t;
scanf("%d",&t);
for(int q=;q<=t;q++){
scanf("%d%d%d",&n,&c1,&c2);
for(int i=;i<n;i++){
scanf("%d",&w[i]);
}
init();
for(int i=;i<=idx;i++){
for(int j=(<<n)-;j>=s[i];j--){
if((s[i]|j)==j){
dp[j]=min(dp[j],dp[j-s[i]]+);
}
}
}
printf("Scenario #%d:\n",q);
printf("%d\n\n",dp[(<<n)-]);
}
return ;
}
dfs记忆化搜索：
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h> using namespace std; int s1[];//存储可以被c1货车一次性搬走的家具的不同状态，二进制下1代表还没搬，0代表已搬走了
int s2[];//存储可以被c2货车一次性搬走的家具的不同状态，二进制下1代表还没搬，0代表已搬走了
int s1s2[];//存储可以一次性被两辆车运载的情况
int vis[];//vis[i]:若i能一次性被两辆车运走，则vis[i]=1;
int index1,index2,index3;
int dp[(<<)+];//dp[i]表示剩余家具状态为i时最少要搬几次
int t,n,c1,c2,load;
int w[];
int ans; void init(){
for(int i=;i<(<<n);i++){
load=; //忘记每次开始的时候load=0了；
for(int p=;p<n;p++){
if(i&(<<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]!=-)
return dp[s];
for(int i=;i<index3;i++){
if(s1s2[i]==s){
dp[s]=;
return dp[s];
}
}
dp[s]=; for(int i=;i<index3;i++){
ss=s1s2[i];
if((ss|s)==s){
dp[s]=min(dp[s],dfs(s-ss)+);
}
}
return dp[s];
}
int main()
{
scanf("%d",&t);
for(int i=;i<=t;i++){
memset(dp,-,sizeof(dp));
memset(vis,,sizeof(vis));
index1=index2=index3=;
scanf("%d%d%d",&n,&c1,&c2);
for(int j=;j<n;j++)
scanf("%d",&w[j]);
init();
int s11,s22;
//先将可以一次性被两辆车运走的情况给存起来
for(int m=;m<index1;m++){
for(int j=;j<index2;j++){
s11=s1[m];
s22=s2[j];
if((s11&s22)==){
vis[s11|s22]=;
}
}
}
for(int m=;m<(<<n);m++){
if(vis[m]==){
s1s2[index3]=m;
index3++;
}
}
ans=dfs((<<n)-);
printf("Scenario #%d:\n",i);
printf("%d\n\n",ans);
}
return ;
}