0036算法笔记——【分支限界法】0-1背包问题程序.docx

?问题描述? ? ?给定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达最大.即一个特殊的整数规划问题。? ? ?算法设计? ? ??首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。? ? ?算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。? ? ?例如：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}—{}? ? ? ?算法代码实现如下：? ? ?1、MaxHeap.h[cpp]?view plain?copytemplateclass?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];??????????}????????????MaxHeapT?Insert(const?T?x);?//增??????????MaxHeapT?DeleteMax(T?x);???//删????????????void?Initialize(T?a[],?int?size,?int?ArraySize);????????private:??????????int?CurrentSize,?MaxSize;??????????T?*heap;??//?element?array??};????templateclass?T??MaxHeapT::MaxHeap(int?MaxHeapSize)??{//?Max?heap?constructor.??????MaxSize?=?MaxHeapSize;??????heap?=?new?T[MaxSize+1];??????CurrentSize?=?0;??}????templateclass?T??MaxHeapT?MaxHeapT::Insert(const?T?x)??{//?Insert?x?into?the?max?heap.??????if?(CurrentSize?==?MaxSize)??????{??????????coutno?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;??}????templateclass?T??MaxHeapT?MaxHeapT::DeleteMax(T?x)??{//?Set?x?to?max?element?and?delete?max?element?from?heap.??????//?check?if?heap?is?em