对应POJ题目：点击打开链接
有n件家具和两辆车（容量分别为c1, c2），某人要搬家，问至少需要几次才能把所有家具运完（两辆车必须同时行驶）。
思路：
n很小，可以用二进制保存1 ~ (1<<n) - 1 种状态，每种状态表示几件家具，比如n = 7时。5这个状态，5用二进制表示为 0000101，可以用它表示为第5件家具和第7件家具被选上(或者从右边数起，表示第1和第3件家具)。之后可以枚举每种状态i，之后用两个循环就可完成。转移方程为：dp[i | j] = min{dp[i | j], dp[i] + 1}; （j表示j状态能否一次被两辆车运走，其中i & j 要为空）。dp[x] 表示x状态至少需要几次才能拉走，所以dp[(1<<n) - 1] 就是答案。
再来看怎样求一个状态x，使它能一次被两辆车运走 。先根据状态x的二进制中为1的位置进行对应家具求和sum，然后枚举x的子状态，同样据子状态的二进制中为1的位置进行对应家具求和sum1（表示此sum1要被两辆车中的某辆一次拉走），sum2 = sum - sum1。如果sum1和sum2都符合载重。则状态x能一次被两辆车运走。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
#define M (1<<N)
#define INF (1<<30)
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define SIZE ((1<<n)-1)
int a[N];
int dp[M];
int OK[M];
int c1, c2;
bool Judge(int x)
{
int i, j, t = 0;
int sum1 = 0, sum2 = 0, sum = 0;
for(i=1; i<=x; i=(1<<t)){ /* 对x集合所包含的物品求和 */
if(i & x) sum += a[t];
t++;
}
if(sum > c1 + c2) return 0;
for(i=1; i<=x; i++){ /* 枚举x的子集 */
if((i & x) != i) continue; /* i不是x的子集 */
sum1 = t = 0;
for(j=1; j<=i; j=(1<<t)){
if(j & i) sum1 += a[t];
t++;
}
sum2 = sum - sum1;
if(sum1 <= c1 && sum2 <= c2) return 1;
if(sum2 <= c1 && sum1 <= c2) return 1;
}
return 0;
}
int main()
{
//freopen("in.txt", "r", stdin);
int T, n, w = 0;
int i, j, ans;
scanf("%d", &T);
while(T--)
{
memset(OK, 0, sizeof(OK));
scanf("%d%d%d", &n, &c1, &c2);
for(i=0; i<n; i++) scanf("%d", a + i);
for(i=1; i<M; i++) dp[i] = INF;
for(i=1; i<=SIZE; i++)
if(Judge(i)) OK[i] = dp[i] = 1;
for(i=1; i<=SIZE; i++){
for(j=1; j<=SIZE; j++){
if(i & j) continue; /* 交集不为空 */
if(dp[i] != INF && OK[j])
dp[i|j] = MIN(dp[i|j], dp[i] + 1);
}
}
printf("Scenario #%d:\n%d\n", ++w, dp[SIZE]);
if(T) printf("\n");
}
return 0;
}
原文：http://blog.csdn.net/u013351484/article/details/44900297