算法笔记分支限界法01背包问题.docx

《算法笔记分支限界法01背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问题描述   给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?   形式化描述：给定c>0,wi>0,vi>0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。   算法设计    首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。   算法首先检

2、查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。   例如：0-1背包问题，当n=3时，w={16,15,15},p={45,25,25},c=30。优先队列式分支限界法：处理法则:价值大者优先。{}—>{A}—>{B,C}—>{C，D，E}—>{C，E}—>{C，J，K}—>{C}—>{F，G}—>{G，L，M}—>{G，M}—>{G}—>{N，O}—>{O}—

3、>{}    算法代码实现如下：   1、MaxHeap.h[cpp] viewplain copy1.template  2.class MaxHeap  3.{  4.    public:  5.        MaxHeap(int MaxHeapSize = 10);  6.        ~MaxHeap() {delete [] heap;}  7.        int Size() const {return CurrentSize;}  8.  9.        T Max()   10.        { 

4、         //查  11.           if (CurrentSize == 0)  12.           {  13.                throw OutOfBounds();  14.           }  15.           return heap[1];  16.        }  17.  18.        MaxHeap& Insert(const T& x); //增  19.        MaxHeap& DeleteMax(T& x);   //删  20.  2

5、1.        void Initialize(T a[], int size, int ArraySize);  22.  23.    private:  24.        int CurrentSize, MaxSize;  25.        T *heap;  // element array  26.};  1.  2.template  3.MaxHeap::MaxHeap(int MaxHeapSize)  4.{// Max heap constructor.  5.    MaxSize = M

6、axHeapSize;  6.    heap = new T[MaxSize+1];  7.    CurrentSize = 0;  8.}  9.  10.template  11.MaxHeap& MaxHeap::Insert(const T& x)  12.{// Insert x into the max heap.  13.    if (CurrentSize == MaxSize)  14.    {  15.        cout<<"no space!"<

7、 return *this;   17.    }  18.  19.    // 寻找新元素x的位置  20.    // i——初始为新叶节点的位置，逐层向上，寻找最终位置  21.    int i = ++CurrentSize;  22.    while (i != 1 && x > heap[i/2])  23.    {  24.        // i不是根节点，且其值大于父节点的值，需要继续调整  25.        heap[i] = heap[i/2]; // 父节点下降  26.        i /= 2;      

8、        // 继续向上，搜寻正确位置  27.    }  28.  29.   heap[i] = x;  30