BB_Knapsack：（一） 1、分支限界法介绍 分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解；而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。 2、常见的两种分支限界法

队列式（FIFO）分支限界法：按照先进先出原则选取下一个节点为扩展节点。活结点表是先进先出队列。LIFO分支限界法：活结点表是堆栈。
LC（least cost）分支限界法（优先队列式分支限界法）：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。

FIFO分支限界法搜索策略： §一开始，根结点是唯一的活结点，根结点入队。 §从活结点队中取出根结点后，作为当前扩展结点。 §对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。 §再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 优先队列式分支限界法搜索策略： §对每一活结点计算一个优先级（某些信息的函数值）； §根据这些优先级从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 §再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 3、解决01背包问题算法的思想

01背包问题状态空间树

（二）

_问题描述_

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 _ 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}—>{}

最大树的概念

最大树是每个节点的值都要大于或等于其子节点的值的树。而最大堆就是最大的完全二叉树。因为最大堆是完全二叉树，所以拥有n个元素的堆的高度为[log2(n+1)]。因此如果可以在O(height)的时间内完成插入和删除操作，则其复杂度为O(log2n)。

TIPS: 如将一棵有**_n_个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, _n_**，则有以下关系：

若**_i_ _=_ 1, 则 _i_ 无双亲**

若**_i_ > 1, 则 _i_ 的双亲为ë_i_／2**û

若**2*_i_ <= _n_**, 则 _i_ 的左子女为 2*_i_**，

若**2*_i_**+1 <= _n_**, 则 _i_ 的右子女为2*_i_**+1

若 _i_ 为奇数**, 且**_i_ != 1,

则其左兄弟为**_i_-1**, 若

若 _i_ 为偶数**, 且**_i_ != _n_**, 则其右兄弟为_i_+1**

下面是一个最大堆的图例。这里的第一层和第二层是标记第几层子节点，并不是树的第几层。

1.最大堆的插入：

先来举个栗子说明最大堆的插入问题。这是一个有五个元素的最大堆。如果要插入一个元素，那么插入完成后的结构应该是这样才能保证依旧是完全二叉树：如果插入的元素是1，那很简单，直接作为第二层的元素2的左孩子节点插入即可。但是如果插入的元素是5，也就是比该插入位置的父节点大的话，就需要做一定的调整了。应该把元素2下移为左孩子，同时在判断5能否占据元素2的位置。因为5<20，所以5可以插入在当前位置。插入完成： 16="" 201212="" ![](http:="" img.my.csdn.net="" uploads="" 1355636933_2478.jpg)="" 但是如果想要插入的元素是25呢？="" 那么在这一步便会有所不同：="" 1355636990_9472.jpg)="" 因为25="">20，不满足我们最大堆的要求，所以我们要做的事情和上次一样，先将20移下一层：再将25插入即可。插入完成：下面来总结一下插入的操作。插入算法首先要知道插入完成后的二叉树结构，然后再把要插入的元素一次调整到正确的位置。插入策略从根到叶只有单一路径，每一层的工作耗时O(1)，因此实现插入操作的时间复杂性为O(height)=O(log2n)。

2.最大堆的删除

从最大堆中删除一个元素的时候，该元素从堆的根部移出。以下图为例：如果要从中删除元素21也就是移除堆顶元素。必须移动最后的一个元素，也就是元素2，才能保证它依旧是一个完全二叉树。这样确保它依旧是完全二叉树，但是元素2还没有放入堆中。而根据堆的结构特性，2是不能直接插入根节点的，可以先假设把元素二放在根节点：则需要作一定的调整以便让它保持最大堆的特性。因为根应当是堆的所有数据中最大的那个数，也就是说，根元素应该是元素2，根的左孩子，根的右孩子三者中的最大者。为什么呢？因为本来根的左孩子或右孩子应该是是堆中的第二大元素。移除根之后必有一个是最大的元素，也就是根元素的合适人选。现在再来看看栗子。三者中的最大值是20，所以把它移到了根节点。此时在20的原位置，也就是按次序编号的3位置形成一个空位，由于该位置没有孩子节点，所以元素2可以插入。最后形成了删除完毕的最大堆：下面再来举个栗子，在上面的最大堆里删除元素20。删除之后的结构应该是这样的：所以先把元素10移除。如果直接把10放在根节点并不能形成最大堆。所以把根节点的两个孩子15和2中较大的一个移到根节点。移动完之后发现10还是不能插入，所以再把14往上移一层：这样便会发现元素10可以插入了，于是最终的最大堆如下图所示：下面来总结一下删除的操作。删除算法需要了解删除完成后的完全二叉树结构，先移除最后一个节点，把要删除位置的两个孩子挑选最大的移动到根节点。如果最后一个节点元素能插入则插入，否则重复上述操作直到能插入为止。插入策略从根到叶只有单一路径，每一层的工作耗时O(1)，因此实现插入操作的时间复杂性为O(height)=O(log2n)。

3.最大堆的初始化

很多情况下我们是已经获取了一个有n个元素的无序数组，需要进行最大堆的初始化操作。如果用一次插入的方法，构建非空最大堆，插入操作的总时间为O(log2n)。下面介绍一下利用不同的策略在O(n)的时间里完成堆的初始化。假设开始数组a[1:10]的关键值分别为[20，12，35，15，10，80，30，17，2，1]。<详情见最上面的TIPS性质！> 这些数值可以通过逐层输入的方法构成一棵完全二叉树：接下来做的便是从下往上依次调整。先来说一下大体思路。为了将完全二叉树转化成最大堆，先从第一个具有孩子的节点下手（从下往上从后往前看 i为数组编号也是二叉树的顺序排序编号，根据这个性质即是从数组找数组中的元素！）。从图中来看就是节点10。这个元素在数组中的位置为i=[n/2]。如果以此元素为根的子树已经是最大堆，则不需调整，否则必须调整使其成堆。随后依次检查以i-1，i-2等节点为根的子树，直到检测到整个二叉树的根节点。下面来看这个栗子。第一次调整检验，i=5的时候：此时这棵子树是满足最大堆的要求的，所以我们不用调整它。接下来检查下一个节点，也就是i=4的情况：因为15<17，所以这棵子树不满足最大堆的条件。为了把它变身成为最大堆，可以把子节点中最大的数与根节点元素交换，也就是可用15与17交换，得到的树效果如下：此时i=4的位置已经是最大堆了。接下来便是i=3的情况，和前面几次一样，将35与其孩子节点中最大的元素交换即可：如此这般，i=3便也解决了。那么当i=2的时候，首先执行一次交换，确保了i=3为根的子树的前两层是最大堆：下一步，将元素12与位置为4的节点的两个孩子中较大的一个元素进行比较。由于12<15，所以15被移到了位置4，12暂时移入了位置8。因为8位置没有子节点，所以将12插入，完成这一步调整。最后还剩i=1的情况：当i=1时，此刻以i=2和i=3为根节点的子树们均已经是最大堆。然后20<(max[35,30]),所以把80作为最大根，把80移入1位置：位置3空出，因为20<(max[35,30])，所以元素35插入位置3，元素20插入元素6。最终形成的最大堆如图所示：总结一下初始化最大堆的过程，大致就是从下往上依次检测所有子树是否为最大堆，如果不是把他们调整成最大堆，并将子树的根节点放置到合适的位置不影响下面的子树的最大堆结构。下面附上源码以供加深理解：

ifndef MAXHEAP_H

define MAXHEAP_H

include

using namespace std;
const int DefaultSize=50;
template class MaxHeap{ // K为关键码的数据类型，E为记录的结构类型
public:
MaxHeap(int sz = DefaultSize);//构造函数：建立空堆
MaxHeap(E arr[], int n); //构造函数：通过一个数组建堆
~MaxHeap() {
delete []heap;
}
bool Insert(const E &x);
bool RemoveMax(E &x);
bool IsEmpty()const{
return currentSize == 0;
}
bool IsFull()const{
return currentSize == maxHeapSize;
}
void MakeEmpty(){
currentSize = 0;
}
void Swap(int i, int j){
E tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
void output(){//自定义函数，顺序输出最大堆元素
for(int i = 0; i
//MaxHeap ::Maxheap(int sz) {
// maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
// heap = new E[maxHeapSize];
// assert(heap);
// currentSize = 0;
//}
//
// 构造函数：建立空堆
template MaxHeap::MaxHeap(int sz){
maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
heap = new E[maxHeapSize];
assert(heap);
currentSize = 0;
}
// 构造函数：通过一个数组建堆
template MaxHeap::MaxHeap(E arr[], int n){
maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
heap = new E[maxHeapSize];
assert(heap);
for (int i = 0; i < n; i++ ){
heap[i] = arr[i];
}
currentSize = n;
int currentPos = (currentSize-2)/2; //找最初调整位置:最后分支结点
while (currentPos >= 0){ //自底向上逐步扩大形成堆
siftDown(currentPos, currentSize -1); //局部自上向下下滑调整
currentPos—; //再向前换一个分支结点
}
}
//私有函数：最大堆的下滑调整算法
template void MaxHeap::siftDown(int start, int m){
int i = start, j = 2i+1;//j是i的左子女位置
E temp = heap[i];
while (j <= m){//检查是否到最后位置
//让j指向两子女中的小者
if (j < m && heap[j] < heap[j+1]){
j++;
}
if (temp >= heap[j]){
break;
}
else{
heap[i] = heap[j];
i = j;
j = 2j+1;
}
}
heap[i] = temp; //回放temp中暂存的元素
}
// 私有函数：最大堆的上滑调整算法
template void MaxHeap::siftUp(int start){
int j = start, i = (j-1)/2;
E temp = heap[j];
while (j > 0){ //沿父结点路径向上直达根
if (heap[i] >= temp) {
break;
}
else{
heap[j] = heap[i];
j = i;
i = (i-1)/2;
}
}
heap[j] = temp; //回放temp中暂存的元素
}
// 公共函数: 将x插入到最大堆中
template bool MaxHeap::Insert(const E &x){
if (currentSize == maxHeapSize){ //堆满
cerr << “Heap Full” << endl;
return false;
}
heap[currentSize] = x; //插入
siftUp(currentSize); //向上调整
currentSize++; //堆计数加1
return true;
}
// 公共函数：最大堆的删除算法
template bool MaxHeap::RemoveMax(E &x){
if (!currentSize){ //堆空, 返回false

    cout << "Heap empty" << endl;
    return false;
}
x = heap\[0\];        // 返回最大元素
heap\[0\] = heap\[currentSize-1\];    //最后元素填补到根结点
currentSize--;
siftDown(0, currentSize-1);        //自上向下调整为堆
return true;

}

endif

另一个的实现：

//优先队列：堆MaxHeap的定义与使用
#include
using namespace std;
void OutOfBounds(){
    cout<<"Out Of Bounds!"<<endl;
}
void BadInput(){
    cout<<"Bad Input!"<<endl;
}
void NoMem(){
    cout<<"No Memory!"<<endl;
}
template
class MaxHeap{
    public:
        MaxHeap(int MaxHeapSize = 10);
        int Size()const{return CurrentSize;}
        T Max(){
            if (CurrentSize == 0)
                throw OutOfBounds();
            return heap\[1\];
        }
        MaxHeap& Insert(const T&x);
        MaxHeap& DeleteMax(T&x);
        void Initialize(T a\[\],int size,int ArraySize);
        void Output(ostream& out)const;
        int CurrentSize;
        int MaxSize;
        T *heap;//元素数组
};
//输出链表
template
void MaxHeap::Output(ostream& out)const{
    for (int i= 0;i<CurrentSize;i++)
    {
        cout<<heap\[i+1\]<<"  ";
    }
    cout<<endl;
}
//重载操作符
template
ostream& operator<<(ostream& out,const MaxHeap&x){
    x.Output(out);
    return out;
}
template
MaxHeap::MaxHeap(int MaxHeapSize /* = 10 */){
    MaxSize = MaxHeapSize;
    heap = new T\[MaxSize+1\];
    CurrentSize = 0;
}
//将x插入到最大堆中
template
MaxHeap& MaxHeap::Insert(const T&x){
    if(CurrentSize==MaxSize)
        throw NoMem();
    //为x寻找插入位置
    //i从新的叶结点开始，并沿着树慢慢上升
    int i = ++CurrentSize;
    while(i!=1&&x>heap\[i/2\]){
        //不能把x放到heap\[i\]
        heap\[i\] = heap\[i/2\];//将元素下移
        i/=2;
    }
    heap\[i\] = x;
    return *this;
}
//将最大的元素放到x并从堆中删除
template
MaxHeap& MaxHeap::DeleteMax(T&x){
    //检查堆是否为空
    if(CurrentSize==0)
        throw new std::exception("OutOfBounds");
    x = heap\[1\];                    //取出最大元素并放入x中
    T y = heap\[CurrentSize\];        //y为最后一个元素
    CurrentSize--;
    //从根开始为y寻找合适的位置
    int i = 1;          //堆的当前节点
    int ci = 2;         //i的孩子
    while(ci<=CurrentSize){
        //heap\[ci\]应该是较大的孩子
        if(ci<CurrentSize&&heap\[ci\]<heap\[ci+1\]) ci++; //能否把y放入heap\[i\] if(y>=heap\[ci\])
            break;
        heap\[i\]=heap\[ci\];
        i = ci;
        ci = 2*ci;
    }
    heap\[i\]=y;
    return *this;
}
//把最大堆初始化为数组a
template
void MaxHeap::Initialize(T a\[\],int size,int ArraySize){
    delete \[\]heap;
    heap = a;
    CurrentSize = size;
    MaxSize = ArraySize;//数组空间大小
    //产生一个最大堆
    for (int i = CurrentSize/2;i>=1;i--){
        T y = heap\[i\];      //子树的根
        //寻找放置y的位置
        int c = 2*i;    //c的父节点是y的目标位置
        while(c<=CurrentSize){
            //heap\[c\]应该是较大的同胞节点
            if(c<CurrentSize&&heap\[c\]<heap\[c+1\]) c++; //能否把y放入heap\[c/2\] if(y>=heap\[c\])       //能把y放入heap\[c/2\]
                break;
            //不能把y放入heap\[c/2\]
            heap\[c/2\]=heap\[c\];  //将孩子上移
            c=2*c;              //下移一层
        }
        heap\[c/2\] = y;
    }
}
template
void HeapSort(T a\[\],int n)
{
    MaxHeapH;
    H.Initialize(a,n,20);
    T x;
    for (int i=n-1;i>=1;i--)
    {
        H.DeleteMax(x);
        a\[i+1\]=x;
    }
}
int main(){
    MaxHeapmyHeap;
    const int number = 10;
    int myArray\[number+1\] = {-1,6,8,4,2,1,3,0,5,7,9};
    myHeap.Initialize(myArray,number,20);
    cout<<myHeap<<endl;
    HeapSort(myArray,number);
    for (int j =1;j<=number;j++)
    {
        cout<<myArray\[j\]<<"  ";
    }
    cout<<endl;
    return 0;
}

上进心的男生是有魅力的。不论是学习还是之后工作，有上进心的男生都是发光哒。

MaxHeap_KnapsackofBranchandBound

最大树的概念

1.最大堆的插入：

2.最大堆的删除

3.最大堆的初始化

ifndef MAXHEAP_H

define MAXHEAP_H

include

include

endif