算法：poj 2923 Relocation （枚举+背包 | 状态压缩+01背包）

算法：poj 2923 Relocation （枚举+背包 | 状态压缩+01背包）2014-01-10 csdn shuangde800题目大意：

有N件家具，每件的重量为（1 ≤ wi ≤ 100），用两辆车把他们来运送到目的地。这两辆车的限载重量分别为C1, C2（1 ≤ Ci ≤ 100） , 问最少几趟可以把所有家具运送到目的地。

这两辆车每趟都必须一起走，即使某辆车没载东西。

思路：

（一）

先上自己的方法：

枚举第一辆车可能载的家具的所有组合情况，那么用二进制来表示状态则共有 1<<n ，如果二进制的第i位上是1，那么就表示第i件家具是由第一辆车运的。

这样就相当于把所有家具分成了两组，一组给第一辆车运，另一组给第二辆车运。

然后分别对这两组数据计算，分别最少几次可以运完，这样，问题就转换为了：给n个家具，和一辆限载重量c的车，这辆车最少几次可以运完。

由贪心的思想可以知道，每次运送应该尽可能的装满这辆车，那么用01背包，背包容量为限载重量c，每个家具的重量即是价值也是耗费， f[c]就是这次运送的。选择完一次后，把那些选择过的家具删除掉，继续再做 01背包选择，直到所有家具全部选择完。至于记录选择了哪些家具，方法和记录路径一样。

然后，这两辆车分别运送次数取较大的，就是这个枚举到的这个方案的最少次数。

（二）

这个方法是学习的，网上的基本都是这个方法，不再细讲。

大概思路是，用二进制表示选择状态，先预处理所有选择的组合，看这个组选择的家具能否被两辆车子一次运过去，如果可以的话就“打包”起来看作是一个物体，然后再对所有物体进行01背包。

代码：

方法一：

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<vector>#include<string>#define MP make_pair#define SQ（x） （（x）*（x））const double PI = acos（-1.0）;const int INF = 0x3f3f3f3f;using namespace std;typedef long long int64;const int MAXN = 12;int n, m;int c1, c2;int f[110];int w[MAXN];int ans;bool path[MAXN][110];vector<int>w1, w2;bool check（int x）{for（int i=0; i<n; ++i）{if（（x>>i）&1）{if（w[i]>c1） return false;}else{if（w[i]>c2） return false;}} return true;}void init（int x）{w1.clear（）; w2.clear（）;for（int i=0; i<n; ++i）{if（（x>>i）&1）{w1.push_back（w[i]）;}elsew2.push_back（w[i]）;}}void update（vector<int>&w, int i, int j）{if（i<0） return ;int tmp = w[i];if（path[i][j]）{w.erase（w.begin（）+i）;update（w, i-1, j-tmp）;}elseupdate（w, i-1, j）;}int counter（vector<int>& w, int c）{if（w.size（）==0）return 0; int cnt = 0;do{cnt++;if（cnt >= ans） return cnt;memset（f, 0, sizeof（f））;memset（path, 0, sizeof（path））;for（int i=0; i<w.size（）; ++i）{for（int v=c; v>=w[i]; --v）{if（f[v-w[i]]+w[i] >= f[v]）{f[v] = f[v-w[i]]+w[i];path[i][v] = 1;}}}update（w, w.size（）-1, c）;}while（w.size（））;return cnt;}int main（）{int nCase, cas=1, x;scanf（"%d", &nCase）;while（nCase--）{printf（"Scenario #%d:
", cas++）;scanf（"%d%d%d", &n,&c1,&c2）;for（int i=0; i<n; ++i）scanf（"%d", &w[i]）;ans = INF;int sta = 0;while（sta < （1<<n））{if（！check（sta））{sta++;continue; }init（sta）;int cnt1 = counter（w1, c1）;int cnt2 = counter（w2, c2）;ans = min（ans, max（cnt1, cnt2））;sta++;}printf（"%d

", ans）;}return 0;}