装载问题

有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且w1+w2+…+wn<=c1+c2。

装载问题要求确定，是否有一个合理的装载方案可将这n个集装箱装上这2搜轮船。如果有，找出一种方案。

分析：如果一个给定的装载问题有解，则采用下面的策略可以得到最有装载方案。

（1）首先将第一艘轮船尽可能装满；（2）然后将剩余的集装箱装上第二艘轮船。

将第一艘轮船装满等价于选取全体集装箱的一个子集，使该子集的集装箱重量之和最接近c1。

递归回溯

#include   
using namespace std;  

typedef int Type;  

template class Loading;  
template  
Type MaxLoading(Type w[], Type c, int n, int bestx[]);  

template  
class Loading  
{  
public:  
    friend Type MaxLoading(Type w[], Type c, int n, int bestx[]);  
private:  
    void Backtrack(int i);  
    int n,          //集装箱数  
        *x,         //当前解  
        *bestx;     //当前最优解  
    Type* w,        //集装箱重量数组  
        c,          //第一艘轮船的载重量  
        cw,         //当前载重量  
        bestw,      //当前最优载重量  
        r;          //剩余集装箱重量  
};  

template  
void Loading::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];" 当前处理的是第i个集装箱，r是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 += w[i];//处理完右子树 回上一层时要加上这层的重量  
}  


template  
Type MaxLoading(Type w[], Type c, int n, int bestx[])  
{//返回最优载重量  
    Loading X;  
    //初始化X  
    X.x = new int[n+1];  
    X.w = w;  
    X.c = c;  
    X.n = n;  
    X.bestx = bestx;  
    X.bestw = 0;  
    X.cw = 0;  
    //初始化r  
    X.r = 0;  
    for(int i=1; i<=n; ++i) x.r +="w[i];" x.backtrack(1); delete [] x.x; return x.bestw; } int main(int argc, char* argv[]) { n; type c; cout << "输入集装箱数目:" endl; cin>> n;  
    Type *w=new Type[n+1];  
    int *bestx=new Type[n+1];  
    cout<<"输入"<>w[i];  
    cout << "输入第一艘轮船的载重量c：" << endl;  
    cin >> c;  

    cout << MaxLoading(w, c, n, bestx) << endl;  

    for(int i=1; i<=n; ++i) cout<< bestx[i] << ","; cout "press the enter key to exit"; cin.ignore(cin.rdbuf()->in_avail()+1);  
    return 0;  
}

迭代回溯

#include  
using namespace std;  

typedef int Type;  

template  
Type MaxLoading(Type w[], Type c, int n, int bestx[])  
{//迭代回溯法  
    //返回最优载重量及其相应解  
    //初始化根结点  
    int i=1; //当前层  
    // x[1:i-1]为当前路径  
    int *x = new int[n+1];  
    Type bestw=0,       //当前最优载重量  
        cw=0,           //当前载重量  
        r=0;            //剩余集装箱重量  
    for(int j=1; j<=n; ++j) r+="w[j];" 搜索子树 while(true) { while(i<="n" && cw+w[i]<="c)" 进入左子树 r-="w[i];" cw+="w[i];" x[i]="1;" i++; } if(i>n)  
        {//到达叶结点  
            for(int j=1; j<=n; ++j) bestx[j]="x[j];" bestw="cw;" }else { 进入右子树 r-="w[i];" x[i]="0;" i++; } while(cw+r<="bestw)" 当前最优载重量>= 当前载重量 + 剩余集装箱重量  
        {//剪枝回溯  
            i--;  
            while(i>0 && !x[i])  
            {//从右子树返回  
                r+=w[i];  
                i--;  
            }  
            if(i==0)  
            {  
                delete [] x;  
                return bestw;  
            }  
            //进入右子树  
            x[i]=0;  
            cw-=w[i];  
            i++;  
        }  
    }  
}  

int main(int argc, char* argv[])  
{  
    int n;  
    Type c;  
    cout << "输入集装箱数目:" << endl;  
    cin >> n;  
    Type *w=new Type[n+1];  
    int *bestx=new Type[n+1];  
    cout<<"输入"<>w[i];  
    cout << "输入第一艘轮船的载重量c：" << endl;  
    cin >> c;  

    cout << MaxLoading(w, c, n, bestx) << endl;  

    for(int i=1; i<=n; ++i) cout<< bestx[i] << ","; cout "press the enter key to exit"; cin.ignore(cin.rdbuf()->in_avail()+1);  
    return 0;  
}

Pete Yuan

Comments