poj 2923 Relocation （枚举+背包 | 状态压缩+01背包）-白红宇

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

阅读量：4072 次

发布时间：2019-05-25

本文共 2766 字，大约阅读时间需要 9 分钟。

链接：

题目大意：

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

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

思路：

(一)

先上自己的方法：

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

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

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

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

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

（二）

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

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

代码：

方法一：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #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
           
            w1, w2;bool check(int x){ for(int i=0; i
            
             >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
             
              >i)&1){ w1.push_back(w[i]); }else w2.push_back(w[i]); }}void update(vector
              
               &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
               
                & 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[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

方法二：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #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 = 15;int n, m;int c1, c2;int w[MAXN], d[2000];int sta[2000], idx;bool check(int x){ int sum = 0 ; for(int i=0; i<=c1; ++i) d[i] = 0; d[0] = 1; for(int i=0; i
           
            >i)&1){ sum += w[i]; for(int v=c1; v>=w[i]; --v) d[v] = max(d[v], d[v-w[i]]+w[i]); } if(sum > c1+c2) return false; return sum-d[c1] <= c2;}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
            
             =0; --j){ if(d[j] == INF) continue; if((j&sta[i]) == 0){ d[j|sta[i]] = min(d[j|sta[i]], d[j]+1); } } } printf("%d\n\n", d[(1<

转载地址：http://hpzni.baihongyu.com/

你可能感兴趣的文章