装载问题（回溯法过程和方案选取）

装载问题（回溯法过程和方案选取）

一、问题描述

有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi,且

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

二、问题分析

主要思想：将第一艘船尽可能装满，剩余的装入第二艘船。

1.n和t是什么？

• n是解向量的分量的个数，t指的是当前要确定第t个分量。

2.框架中的解向量，f(n,t)和g(n,t)在这里是什么？

• 在这个问题中，我们一共要确定n个集装箱的取或者不取， 每一个节点都只有两个子节点，分别对应0和1，因此解向量是n维的01向量。
• f(n,t)和g(n,t)一般指的未被搜索过的子树的最小编号和最大编号）

3.是np问题

• 
• c1!=c2子集和问题
• c1==c2集合划分问题

4.运用框架（解空间）：子集树

void backtrack(int t){
    if(t>n) output(x);
    else
        for(int i=0;i<=1;i++){//只有两个儿子
            x[t]=i;
            if(legal(t)) backtrack(t+1);
        }
}

5.约束

• 可行性约束：装进第一个集装箱的重量当然不可以比它的容量大。
  •      
• 限界函数：

  •    ，
  •   当前载重量+剩余集装箱的重量（注意在cw的构建过程中被赋予0的xi不属于剩余的，也就是它是已经表明过不选取的）
  • 如果要选择第t个分量：目前的重量加上剩余的所有重量，都没有当前最优解的重量大，那还进一步考虑这个解分支干什么呢？剪掉！说明你目前的解不可取，你可以回去改一改路径上的x分量（当然你应该最先考虑换一个x[t-1]试一试）

①递归法

class loading{
        friend int MaxLoading(int w[],int c, int n,int bestx[]);
    private:
        void backtrack(int t);
        int n,*x,*bestx;//件数，当前解向量，当前最优解向量
        int *w,cw,r,bestw; //重量信息，目前部分解的重量，目前剩余物品的总重量，最优解的重量
};

void loading::backtrack(int t){
    //已经到达叶子节点，一定是最优解
    if(t>n){
        for(int i=0;i<n;i++) 
            bestx[i]=x[i];
        bestw=cw;
        return;
    }
     r-=w[t];
    //考虑左子树选择t
    if(cw+w[t]<=c){ //可以放进去的话,为1的左子树可以进入
        cw+=w[t];
        x[t]=1;
        backtrack(t+1);
        cw-=w[t];
    }
    //考虑右子树不选择t
    if(cw+r<bestw){//就算其余的全部放进去都没有当前最优解的bestw大，那就剪枝，这个点变为死结点
        r+=w[t];
        return;
    }
    //为0的右子树可以进入
    x[t]=0;
    backtrack(t+1);
    //这个点变为死结点了，回溯
    r+=w[t];
}

int MaxLoading(int w[],int c,int n,int bestx[]){
    loading 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;
    X.r=0;
    for(int i=1;i<=n;i++){
        X.r+=w[i];
    }
    //从第一个结点开始
    X.backtrack(1);
    delete[]X.x;
    return X.bestw;
}

②迭代法

每次我们都优先往左子树深入，直到无法进入（放不下），被迫选择右子树。过程中可能会出现这样的情况：选择了某个结点的右子树后发现，即使剩下所有集装箱都放入也没有当前最优解的重量大，这时候我们回溯。

int MaxLoading(int w[],int c,int n, int bestx[]){
    //初始化
    int cw=0,r=0,t=1,x[n+1];
    for(int i=1;i<=n;i++)
        r+=w[i];
    //没有搜索完整棵树
    while(t>0){
        //左子树，能放进去就放进去
        while(t<=n&&cw+w[t]<c){
            cw+=w[t];
            r-=w[t];
            x[t]=1;
            t++;
        }
        //如果已经将全部的物品选择完毕,那一定是当前的最优解
        if(t>n){
            for(int i=1;i<=n;i++)
                bestx[i]=x[i];
            bestw=cw;
        }
        //右子树，如果剩下的空间放不下第t个物品
        else{
            r-=w[t];//不选t
            x[t]=0;
            t++;
        }
        while(cw+r<=bestw){//后面的全部加上都没有bestw优，回到之前的某一位重新选择
            t--;
            while(t>0&&!x[t]){//回到最近的1，修改它
                r+=w[t];
                t--;
            }
            if(t==0) break;//最优的解已经无法超越了，退到了极致
            x[t]=0;//修改1为0
            cw-=w[t];
            t++;
        }
    
    }
    return bestw;
}

——参考自王晓东《算法设计与分析》（第5版）