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

题目大意：

有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]);
        }else
            w2.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);
    }else
        update(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:\n", 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\n\n", ans);
    }
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， path
， return
， 背包问题
， 状态
， c 回溯 背包
， 01背包
， 01背包类型
， 二进制状态压缩dpacm
背包
0551 6541 2923、136 7512 2923、a2923、astm f2923、2923 28 6，以便于您获取更多的相关知识。