背包分支限界.docx

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

1、01背包分支限界思想：借助大顶堆来实现优先队列，构造大顶堆(按优先队列中所能达到的最大价值来构造这个大顶堆)，实现对堆中元素的插入和删除；在回溯法的基础上改进，首先对物品按单位权重非递减排序，堆中存放的是每一个当前物品所能达到的情况：1.　将第一个单位权重最大的物品插入大顶堆中，并用回溯法中计算边界条件的函数计算出该物品放入背包时所能达到的最大价值，用这一队列最后一个结点记录下当前得到的队列的情况，它可以得到的最大值(double型)，用它该取的下一层次号，所达到的最大价值，所占用背包的体积；2．如果物品层次号（从0开始）小于

2、总个数，取出堆顶元素，对将要遍历到的这一层次上的物品判断选择取与不取的情况．若已经占用的体积＋该物品的体积不超过背包体积，则该物品可以放入，即可以是左儿子结点,isLchild=true,将这一结点加入优先队列并放入大顶堆中；若右子树可能存在最优解，isLchild=false,即不放该物品时可能达到的最大价值(double型变量)>＝放入该物品时当前背包达到的最优解，则也将这一结点加入优先队列中并放入大顶堆中；3.　重复步骤2.感觉算法比较费力，对于01背包来说，由于不满足贪心的性质，所以分支限界在构造好了堆的前提下，它要比

3、回溯法好．代码：头文件：主要为大顶堆的构造，大顶堆中元素的插入，删除；插入时：先将要插入的结点放入堆中最后一个元素的位置，然后自下向上调整．删除时：因为当取出了堆顶元素后，需要对堆中剩余元素调整(堆从标号1开始)．将堆中最后一个元素放在堆顶的位置，然后自上向下调整成为一个新的大顶堆．#defineheader#includeusingnamespacestd;constintMAXN=0x0fffff;typedefstructNode{Node*par;boolisLchild;};typedefstru

4、ctHeapNode{Node*par;//指向此优先队列中所包涵的所有结点doublecp,cw;//当前达到的价值，重量doubleup;//此优先队列所能达到的最大价值intlevel;//它所处的层次}*HP;typedefstructHeap{inthsize;//堆中元素个数HeapNode*heapnodes;//堆中存放可能的解}*BigHeap;//用大顶堆来实现的优先队列BigHeapbigHeap;HeapNodeGetMax(inti)//取出一个最大结点，并向下调整{HeapNodetempNode,

5、maxNode=bigHeap->heapnodes[i];//堆从1开始tempNode=bigHeap->heapnodes[i]=bigHeap->heapnodes[bigHeap->hsize--];//将最后一个结点提升，并使hsize-1intj;for(j=i<<1;j<=bigHeap->hsize;j<<=1)//开始向下调整{if(jhsize&&bigHeap->heapnodes[j].upheapnodes[j+1].up)++j;//j为最大的那个结点if(

6、tempNode.up>=bigHeap->heapnodes[j].up)break;bigHeap->heapnodes[i]=bigHeap->heapnodes[j];//子结点上移i=j;}bigHeap->heapnodes[i]=tempNode;returnmaxNode;}voidInsertNode(HeapNodenode)//插入一个新结点，并自下向上调整{inti;for(i=++bigHeap->hsize;bigHeap->heapnodes[i/2].up>=1)bigHe

7、ap->heapnodes[i]=bigHeap->heapnodes[i/2];//父结点下移bigHeap->heapnodes[i]=node;}BigHeapinit(intn){bigHeap=(BigHeap)malloc(sizeofHeap);bigHeap->hsize=0;bigHeap->heapnodes=(HeapNode*)malloc((n+1)*sizeofHeapNode);bigHeap->heapnodes[0].up=MAXN;returnbigHeap;}Main函数：基本上和回溯法中

8、的大部分代码相同，不同的是用堆来实现优先队列．这里加入了一个数组来记录物品选与不选的情况，因为物品按单位权重排序过后，依然可以很方便的记录物品被选择的情况，最后输出物品选择情况．#include"header.h"#include#include