回溯法-装载问题

子集树问题

和 子集树的0-1背包问题类似，但是没有考虑价格

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

//第五章装载问题
template<class Type>
class Loading{
    friend Type MaxLoading(Type [],Type,int,int[]);
   // private:
   public:
        void Backtrack(int i);
        int n,      //集装箱数
        *x,         //当前解
        *bestx;     //当前最优解


        Type *w,    //集装箱重量数组
        c,          //货轮载重量
        cw,         //当前载重量
        bestw,       //当前最优载重量
        r;             //剩余集装箱重量

};

template <class Type>
void Loading<Type>::Backtrack(int i){
//搜索第i层节点

if(i>n){//到达叶节点
 if(cw>bestw){ for(int j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;    }
 return;
}

//搜索子树
r-=w[i];
if(cw+w[i]<=c){//进入左子树
x[i]=1;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw){//进入右子树
    x[i]=0;
Backtrack(i+1);
}

r+=