这道题算是很经典的状态压缩01背包了， 题意是有一个人要用两辆小汽车搬家， 每辆小汽车都有一个最大载重量， 现在有一些要搬的家具， 告诉你这些家具的重量， 问最少几次能将这些家具搬完（每次两辆汽车必须出动， 即使有一辆车什么都没有装）？ 物品个数不超过10，根据经验一般有10存在的话都要带点暴力的色彩， 那么这道题就是先要预处理所有一次搬走的家具的集合， 然后就将其转化成了01背包的问假设d[i][j]是前i个家具中搬走了j（集合）家具所需要的最少次数那么d[i][j] = min(d[i-1][j], d[i-1][k]) 其中k是j中去掉i集合的家具。这可以使用滚动数组优化一下。。wa点：1：judge函数的编写， 至今找不到我自己想的贪心判断法错那了 2：k的确定，其实这道题的实现应该是从d[i-1][k]推d[i][j],而不是d[i][j]求d[i-1][k].代码如下：
#include <cstdio> #include <cstring> #include <algorithm>using namespace std; const int inf = 0x3f3f3f3f;int Wu[1024+100]; //第i个物品的集合是Wu[i]; int cnt; int n, c1, c2; int weight[20];int f[1024+100];/*int judge(int st) //判断能否一次运走st集合的物品 {int tpweight[15], numtp=0;for(int i=0; i<n; i++){if((st&1) == 1)tpweight[numtp++] = weight[i];st >>= 1;}sort(tpweight, tpweight+numtp);int tpc1=c1, tpc2=c2;for(int i=0; i<2; i++){int now = 0;while(now<numtp && tpc1-tpweight[now]>=0)tpc1 -= tpweight[now++];while(now<numtp && tpc2-tpweight[now]>=0)tpc2 -= tpweight[now++];if(now == numtp) return true;tpc1 = c2; tpc2 = c1;}return false; } */int vis[1100];bool judge(int st) //判断两辆汽车能否一次将st集合中的物品运完 机智值得学习 然而为什么我的错了 {memset(vis, 0, sizeof(vis));vis[0] = 1;int sum = 0;for(int i=0; i<n; i++) if(st&(1<<i)){sum += weight[i];for(int j=c1-weight[i]; j>=0; j--)if(vis[j]) vis[j+weight[i]] = 1;}for(int i=c1; i>=0; i--)if(vis[i] && sum-i<=c2) return true;return false; }int main() {int T, kase=0;scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &c1, &c2);for(int i=0; i<n; i++)scanf("%d", &weight[i]);cnt = 0; //一共有cnt个物品for(int i=1; i<1<<(n); i++){if(judge(i))Wu[cnt++] = i;}memset(f, 0x3f, sizeof(f));f[0] = 0;for(int i=0; i<cnt; i++)for(int j=(1<<n)-1; j>=0; j--){if(j|Wu[i] < (1<<n) && !(j&Wu[i])) //物品i和j不应该有交集 其实不加也可以， 加上更加谨慎f[j|Wu[i]] = min(f[j|Wu[i]], f[j]+1);}printf("Scenario #%d:\n", ++kase);printf("%d\n\n", f[(1<<n)-1]);}return 0; }
