回溯法-最优装载问题

问题描述：

　　有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量是wi，且不能超，即Σwi<=c1+c2。

算法思想：

在给定的装载问题有解的情况下

最优装载方案：

首先将第一艘轮船尽可能的装满；　　

然后将剩余的集装箱装上第二艘轮船。

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

算法设计：

　　先考虑装载一艘轮船的情况，依次讨论每个集装箱的装载情况，共分为两种，要么装(1)，要么不装(0)，因此很明显其解空间树可以用子集树来表示。

　　在算法Maxloading中，返回不超过c的最大子集和，但是并没有给出到达这个最大子集和的相应子集，稍后完善。

　　在算法Maxloading中，调用递归函数Backtrack(1)实现回溯搜索。Backtrack(i)搜索子集树中的第i层子树。

　　在算法Backtrack中，当i>n时，算法搜索到叶结点，其相应的载重量为cw，如果cw>bestw，则表示当前解优于当前的最优解，此时应该更新bestw。

　　算法Backtrack动态地生成问题的解空间树。在每个结点处算法花费O(1)时间。子集树中结点个数为O(2^n)，故Backtrack所需的时间为O(2^n)。另外Backtrack还需要额外的O(n)的递归栈空间。

算法实现：

template <class Type>
class Loading
{
    friend Type MaxLoading(Type [],Type,int);
    private:
        void Backtrack(int i);
        int n;
        Type * w,
            c,
            cw,
            bestw,
            r;//剩余集装箱重量————未考察过的集装箱的重量，并非没有装载的集装箱重量
};
template <class Type>
void Loading<Type>::Backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)
            bestw = cw;
        return;
    }
    r-=w[i];　　　　//计算剩余（未考察）的集装箱的重量，减去当前考察过的对象的重量
    if(cw+w[i] <= c)
    {
        cw += w[i];
        Backtrack(i+1);
        cw -= w[i];
    }
    Backtrack(i+1);
    r+=w[i];　　　　//递归回退返回上一层时，记得修改r的当前值，如果得不到最优解，再取消当前考察的集装箱，标记为未选，因此剩余容量要再加上当前集装箱重量
}
template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
    Loading<Type> X;   //初始化
    X.w = w;
    X.c = c;
    X.n = n;
    X.bestw = 0;
    X.cw = 0;
    X.r = 0;　　//初始化r
    for(int i=1;i<=n;i++)　　//计算总共的剩余（当前为考察过的）集装箱重量
        X.r += w[i];
    X.Backtrack(1);
    return X.bestw;
}