装载问题5种解决方案.doc

算法分析与设计
算法分析与设计
2016/2017（2)
实验题目 装载问题5种解法
学生姓名
学生学号
学生班级
任课教师
提交日期 2017 　
计算机科学与技术学
目录
一问题定义 3
二解决方案 3
1优先队列式分支限界法求解 3
1.1算法分析 3
1。2代码 3
1.3运行结果 13
2队列式分支限界法求解 13
2.1算法分析 13
2.2代码 14
2。3测试截图 22
3回朔法—迭代 22
3.1算法分析 22
3.2代码 22
3。3测试截图 26
4回朔法—递归 26
4.1算法分析 26
4.2代码 27
4.3测试截图 31
5贪心算法 31
5。1算法分析 31
5.2代码 31
5。3测试截图 35

II
一问题定义
有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船,其中集装箱 i 的重量为 w［i]， 且重量之和小于（c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。
二解决方案
1优先队列式分支限界法求解
1.1算法分析
活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解.此时可终止算法。
1.2代码
1。2-1////MaxHeap.h
template〈class T>  
class MaxHeap  
{  
    public:  
        MaxHeap(int MaxHeapSize = 10）；  
        ~MaxHeap（) {delete [] heap；}  
        int Size() const {return CurrentSize；}  
        T Max()   
        ｛          //查找  
           if (CurrentSize == 0)  
           ｛  
                throw OutOfBounds(）；  
           }  
           return heap[1];  
        ｝  

        MaxHeap〈T>＆ Insert(const T& x); //增  
        MaxHeap〈T>& DeleteMax（T＆ x)；   //删  

        void Initialize（T a［］, int size, int ArraySize);  

    private:  
        int CurrentSize, MaxSize;  
        T *heap;  // element array  
｝；  

template〈class T〉  
MaxHeap<T>：:MaxHeap（int MaxHeapSize）  
{// Max heap constructor。  
    MaxSize = MaxHeapSize；  
    heap = new T[MaxSize+1];  
    CurrentSize = 0；  
｝  

template〈class T>  
MaxHeap<T>＆ MaxHeap<T>::Insert（const T& x)  
{// Insert x into the max heap.  
    if (CurrentSize == MaxSize)  
    {  
        cout〈<”no space!"<〈endl；   
        return *this；   
    }  

    // 寻找新元素x的位置  
    // i-—初始为新叶节点的位置，逐层向上,寻找最终位置  
    int i = ++CurrentSize;  
    while (i != 1 && x 〉 heap［i/2]）  
    ｛  
        // i不是根节点，且其值大于父节点的值，需要继续调整  
        heap[i］ = heap［i/2]; // 父节点下降  
        i /= 2;              // 继续向上，搜寻正确位置  
    ｝  

   heap[i] = x；  
   return *this;  
}  

template〈class T>  
MaxHeap〈T〉＆ MaxHeap<T>：：DeleteMax(T＆ x)  
｛// Set x to max element and delete max element from heap.  
    // check if heap is empty  
    if （CurrentSize == 0)  
    ｛  
        cout〈<”Empty heap！”<〈endl；   
        return ＊this;   
    }  

    x = heap[1］; // 删除最大元素  
    // 重整堆  
    T y = heap[CurrentSize--］; // 取最后一个节点，从根开始重整  

    // find place for y starting at root  
    int i = 1,  // current node of heap  
       ci = 2; // child of i  

    while （ci 〈= CurrentSize）   
    ｛  
        // 使ci指向i的两个孩子中较大者  
        if (ci 〈 CurrentSize ＆& heap[ci］ 〈 heap[ci+1])  
        {  
            ci++；  
        ｝  
        // y的值大于等于孩子节点吗？  
        if (y 〉= heap［ci］)  
        {  
            break；   // 是，i就是y的正确位置，退出  
        }  

        // 否,需要继续向下，重整堆  
        heap[i］ = heap[ci]; // 大于父节点的孩子节点上升  
        i = ci;             // 向下一层,继续搜索正确位置  
        ci ＊= 2；  
    }  

    heap[i] = y;  
    return ＊this;  
｝  

template〈class T〉  
void MaxHeap〈T〉:：Initialize(T a［], int size，int ArraySize）  
｛// Initialize max heap to array a.  
    delete ［] heap；  
    heap = a;  
    CurrentSize = size;  
    MaxSize = ArraySize;  

    // 从最后一个内部节点开始,一直到根，对每个子树进行堆重整  
   for （int i = CurrentSize/2; i 〉= 1； i-—）  
   {  
        T y = heap[i]； // 子树根节点元素  
        // find place to put y  
        int c = 2*i; // parent of c is target  
                   // location for y  
        while (c 〈= CurrentSize）   
        {  
            // heap[c］ should be larger sibling  
            if （c 〈 CurrentSize &＆ heap[c] < heap[c+1］)  
            ｛  
                c++；  
            ｝  
            // can we put y in heap［c/2]？  
            if (y 〉= heap［c]）  
            ｛  
                break;  // yes  
            ｝  

            // no  
            heap［c/2］ = heap[c]； // move child up  
            c ＊= 2; // move down a level  
        }  
        heap［c/2] = y;  
    ｝  
｝  
1.2—2///6d3—2。cpp
//装载问题 优先队列式分支限界法求解   
#include "stdafx。h"  
＃include "MaxHeap.h”  
＃include <iostream>  
using namespace std；  

const int N = 4；  

class bbnode;  

template<class Type〉  
class HeapNode  
{  
    template<class Type>  
    friend void AddLiveNode(MaxHeap<HeapNode<Type〉>＆ H，bbnode *E，Type wt,bool ch，int lev);  
    template<class Type>  
    friend Type MaxLoading（Type w[]，Type c，int n,int bestx[］)；  
    public：  
        operator Type() const｛return uweight;}  
    private：  
        bbnode ＊ptr；        //指向活节点在子集树中相应节点的指针  
        Type uweight;       //活节点优先级（上界）  
        int level；          //活节点在子集树中所处的层序号  
};  

class bbnode  
{  
    template<class Type>  
    friend void AddLiveNode(MaxHeap<HeapNode〈Type>〉& H,bbnode *E，Type wt,bool ch，int lev）；  
    template〈class Type〉  
    friend Type MaxLoading(Type w［],Type c,int n，int bestx[］)；  
    friend class AdjacencyGraph；  

    private:  
        bbnode ＊parent;     //指向父节点的指针  
        bool LChild；        //左儿子节点标识  
｝;  

template〈class Type〉  
void AddLiveNode（MaxHeap<HeapNode〈Type〉>＆ H，bbnode *E，Type wt，bool ch,int lev)；  

template〈class Type〉  
Type MaxLoading（Type w[],Type c,int n，int bestx[])；  

int main（)  
｛  
    float c = 70；    
    float w［］ = {0，20，10，26，15}；//下标从1开始    
    int x[N+1]；    
    float bestw；  

    cout<<”轮船载重为："<<c〈<endl;    
    cout<〈"待装物品的重量分别为：”<〈endl；    
    for(int i=1； i〈=N； i++)    
    {    
        cout<<w[i］〈〈" "；    
    }    
    cout〈<endl;    
    bestw = MaxLoading(w，c，N，x)；    

    cout〈<”分支限界选择结果为:"〈<endl；    
    for(int i=1; i<=4; i++）    
    ｛    
        cout〈〈x［i]<<” ”;    
    }    
    cout〈<endl;    
    cout<〈”最优装载重量为："〈〈bestw<<endl；  

    return 0;   
}  

//将活节点加入到表示活节点优先队列的最大堆H中  
template〈class Type〉  
void AddLiveNode（MaxHeap<HeapNode<Type>〉& H，bbnode *E，Type wt,bool ch，int lev）  
｛  
    bbnode ＊b = new bbnode;  
    b—>parent = E;  
    b-〉LChild = ch;  
    HeapNode<Type> N；  

    N.uweight = wt；  
    N。level = lev；  
    N.ptr = b；  
    H。Insert（N）；  
}  

//优先队列式分支限界法，返回最优载重量，bestx返回最优解  
template<class Type>  
Type MaxLoading(Type w［],Type c,int n，int bestx[］）  
{  
    //定义最大的容量为1000  
    MaxHeap<HeapNode〈Type〉〉 H（1000);  

    //定义剩余容量数组  
    Type *r = new Type[n+1］;  
    r［n] = 0；  

    for（int j=n—1； j>0； j——）  
    ｛  
        r[j］ = r［j+1] + w［j+1]；  
    }  

    //初始化  
    int i = 1;//当前扩展节点所处的层  
    bbnode ＊E = 0；//当前扩展节点  
    Type Ew = 0； //扩展节点所相应的载重量  

    //搜索子集空间树  
    while（i!=n+1）//非叶子节点  
    ｛  
        //检查当前扩展节点的儿子节点  
        if（Ew+w［i]〈=c）  
        {  
            AddLiveNode(H，E，Ew+w[i］+r［i],true，i+1);  
        }  
        //右儿子节点  
        AddLiveNode（H，E，Ew+r[i］，false，i+1);  

        //取下一扩展节点  
        HeapNode〈Type〉 N；  
        H.DeleteMax(N）;//非空  
        i = N.level；  
        E = N。ptr；  
        Ew = N.uweight — r[i—1]；  
    ｝  

    //构造当前最优解  
    for（int j=n； j>0; j——）  
    {  
        bestx［j] = E—〉LChild；  
        E = E-〉parent;  
    }  

    return Ew;  
｝  
1.3运行结果
2队列式分支限界法求解
2.1算法分析
在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点.如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记—1,故在取队首元素时,活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。
节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r〈bestw时，可将其右子树剪去,因为此时若要船装最多集装箱，就应该把此箱装上船。另外,为了确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。
为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后,可以根据parent回溯到根节点，找到最优解.
2.2代码
22-1////Queue。h
＃include〈iostream>  
using namespace std;  
template <class T>  
class Queue  
｛  
    public：  
        Queue（int MaxQueueSize=50);  
        ～Queue（）｛delete [] queue；}  
        bool IsEmpty(）const｛return front==rear;｝  
        bool IsFull（）｛return ( （  （rear+1）％MaxSize==front ）?1：0)；｝  
        T Top(） const；  
        T Last（） const;  
        Queue<T>＆ Add(const T＆ x）；  
        Queue〈T〉& AddLeft(const T＆ x)；  
        Queue<T〉＆ Delete（T &x)；  
        void Output（ostream& out）const;  
        int Length（）{return （rear-front）；}  
    private:  
        int front;  
        int rear；  
        int MaxSize;  
        T *queue;  
};  

template〈class T>  
Queue〈T>：:Queue(int MaxQueueSize)  
{  
    MaxSize=MaxQueueSize+1;  
    queue=new T［MaxSize];  
    front=rear=0;  
｝  

template<class T 〉  
T Queue<T〉：：Top（）const  
｛  
    if(IsEmpty()）  
    ｛  
        cout<〈”queue：no element,no!"<〈endl;  
        return 0；  
    }  
    else return queue[（front+1) ％ MaxSize］；  
}  

template〈class T>  
T Queue〈T> ::Last()const  
{  
    if(IsEmpty()）  
    {  
        cout〈<”queue:no element”〈<endl；  
        return 0;  
    }  
    else return queue［rear];  
｝  

template〈class T〉  
Queue<T〉&  Queue<T〉：:Add（const T＆ x）  
｛  
    if(IsFull（))cout〈<"queue:no memory”<<endl;  
    else  
    ｛  
        rear=(rear+1)% MaxSize;  
        queue[rear］=x;  
    }  
    return ＊this；  
}  

template〈class T>  
Queue<T〉＆  Queue<T〉：：AddLeft(const T& x）  
{  
    if(IsFull(）)cout<〈”queue:no memory”〈〈endl;  
    else  
    ｛  
        front=(front+MaxSize—1）％ MaxSize；  
        queue[(front+1）% MaxSize］=x;  
    ｝  
    return *this；  
}  

template<class T>  
Queue<T>＆  Queue<T〉 ：：Delete(T ＆ x)  
｛  
    if(IsEmpty（））cout<<"queue：no element(delete)"〈<endl；  
    else   
    {  
        front=(front+1） ％ MaxSize;  
        x=queue[front］;  
    }  
    return *this；  
}  

template<class T>  
void Queue 〈T>:：Output(ostream＆ out）const  
｛  
    for（int i=rear％MaxSize;i>=(front+1）%MaxSize;i——)  
       out〈〈queue［i］;  
｝  

template<class T〉  
ostream＆ operator 〈〈 (ostream& out，const Queue〈T>& x）  
｛x。Output(out）;return out;}  
2.2—2////6d3—1。cpp
//装载问题 队列式分支限界法求解   
#include ”stdafx.h”  
＃include "Queue.h"  
#include <iostream>  
using namespace std;  

const int N = 4;  

template<class Type〉  
class QNode  
{  
    template〈class Type>  
    friend void EnQueue（Queue〈QNode<Type〉*〉&Q,Type wt,int i,int n，Type bestw，QNode<Type〉＊E，QNode〈Type〉 ＊＆bestE,int bestx[］，bool ch)；  

    template<class Type〉  
    friend Type MaxLoading（Type w[］,Type c,int n,int bestx[］);  

    private：  
        QNode ＊parent;  //指向父节点的指针  
        bool LChild;    //左儿子标识  
        Type weight;    //节点所相应的载重量  
｝;  

template〈class Type〉  
void EnQueue（Queue<QNode〈Type>＊>＆Q,Type wt，int i,int n，Type bestw,QNode<Type〉＊E，QNode<Type〉 *＆bestE,int bestx[],bool ch）；  

template〈class Type>  
Type MaxLoading(Type w［］,Type c，int n，int bestx[］）；  

int main()  
｛  
    float c = 70;    
    float w［］ = {0,20，10，26，15};//下标从1开始    
    int x[N+1];    
    float bestw；  

    cout〈<”轮船载重为："〈〈c<〈endl;    
    cout<<"待装物品的重量分别为："<〈endl；    
    for(int i=1； i<=N； i++)    
    {    
        cout〈<w［i]〈<” ”；    
    ｝    
    cout<<endl；    
    bestw = MaxLoading（w,c，N，x）；    

    cout〈<"分支限界选择结果为：”〈<endl；    
    for（int i=1； i〈=4； i++)    
    {    
        cout<〈x[i]〈<” "；    
    }    
    cout<〈endl；    
    cout<<”最优装载重量为：”<〈bestw〈〈endl；  

    return 0；    
｝  

//将活节点加入到活节点队列Q中  
template<class Type〉  
void EnQueue（Queue〈QNode<Type〉＊〉＆Q,Type wt,int i,int n，Type bestw，QNode<Type>*E，QNode<Type> *＆bestE，int bestx［]，bool ch）  
{  
    if(i == n）//可行叶节点  
    {  
        if（wt == bestw）  
        ｛  
            //当前最优装载重量  
            bestE = E;  
            bestx[n］ = ch；            
        }  
        return;  
    ｝  
    //非叶节点  
    QNode<Type〉 *b；  
    b = new QNode〈Type>;  
    b—〉weight = wt；  
    b—>parent = E;  
    b—〉LChild = ch;  
    Q.Add（b)；  
}  

template〈class Type>  
Type MaxLoading（Type w［］，Type c，int n，int bestx［］）  
｛//队列式分支限界法,返回最优装载重量，bestx返回最优解  
 //初始化  
    Queue〈QNode〈Type〉＊> Q；      //活节点队列  
    Q.Add(0)；                   //同层节点尾部标识  
    int i = 1;               //当前扩展节点所处的层  
    Type Ew = 0,              //扩展节点所相应的载重量  
         bestw = 0,          //当前最优装载重量  
         r = 0;            //剩余集装箱重量  
    for（int j=2； j<=n； j++)  
    ｛  
        r += w[j]；  
    }  

    QNode<Type> *E = 0，           //当前扩展节点  
                *bestE；       //当前最优扩展节点  

    //搜索子集空间树  
    while(true)  
    ｛  
        //检查左儿子节点  
        Type wt = Ew + w［i］；  
        if(wt <= c）//可行节点  
        ｛  
            if（wt〉bestw）  
            {  
                bestw = wt；  
            ｝  
            EnQueue（Q，wt,i,n,bestw,E,bestE，bestx，true);  
        }  

        //检查右儿子节点  
        if（Ew+r〉bestw）  
        ｛  
            EnQueue（Q,Ew,i,n,bestw,E,bestE,bestx，false)；  
        }  
        Q。Delete(E）;//取下一扩展节点  
        if(！E）//同层节点尾部  
        {  
            if（Q。IsEmpty（)）  
            {  
                break;  
            }  
            Q.Add(0)；       //同层节点尾部标识  
            Q.Delete（E）;    //取下一扩展节点  
            i++；            //进入下一层  
            r—=w［i］；        //剩余集装箱重量  
        }  
        Ew  =E-〉weight；      //新扩展节点所对应的载重量  
    }  
    //构造当前最优解  
    for（int j=n-1; j〉0; j——)  
    ｛  
        bestx[j］ = bestE—>LChild；  
        bestE = bestE-〉parent；  
    ｝  
    return bestw；  
}  
2。3测试截图
3回朔法—迭代
3.1算法分析
用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重量之和小于(c1 + c2)可剪去不满足约束条件的子树用cw记当前的装载重量，即cw=(w1x1+w2x2+...+wjxj),当cw〉c1时,以节点Z为根的子树中所有节点都不满足约束条件,因而该子树中解均为不可行解，故可将该子树剪去。
3。2代码
＃include 〈iostream>  
using namespace std;   

template<class Type〉  
Type MaxLoading（Type w［ ］， Type c， int n， int bestx[ ])；  
int main()  
{     
    int n=3，m；  
    int c=50,c2=50；  
    int w［4]={0，10，40,40}；  
    int bestx［4］；  

    m=MaxLoading（w, c, n, bestx);  

    cout<〈"轮船的载重量分别为：”<<endl；  
    cout<〈”c（1）=”<〈c〈<”,c(2）="<〈c2〈〈endl；  

    cout<<"待装集装箱重量分别为：”<〈endl；  
    cout<<”w（i）=”；  
    for （int i=1;i<=n;i++）  
    {  
        cout<〈w［i]<〈” "；  
    }  
    cout〈〈endl；  

    cout〈<”回溯选择结果为："<〈endl;  
    cout<〈”m（1）=”<〈m〈<endl;  
    cout<<"x(i）=";  

    for (int i=1；i〈=n;i++)  
    ｛  
        cout<〈bestx[i]<<" ”；  
    ｝  
    cout〈〈endl；  

    int m2=0；  
    for （int j=1;j〈=n；j++）  
    ｛  
        m2=m2+w[j］*(1-bestx[j]）;  
    ｝  
    cout<<”m(2）=”<<m2<〈endl;  

    if(m2>c2)   
    ｛  
        cout<<”因为m(2)大于c(2),所以原问题无解！”〈〈endl；  
    }  
    return 0；  
｝  

template 〈class Type〉  
Type MaxLoading(Type w