01背包分支分析.doc

背包问题:给定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}—{} //0-1背包问题 分支限界法求解 #include stdafx.h #include MaxHeap.h #include iostream using namespace std; class Object { templateclass Typew,class Typep friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); public: int operator = (Object a) const { return d=a.d; } private: int ID; float d;//单位重量价值 }; templateclass Typew,class Typep class Knap; class bbnode { friend Knapint,int; templateclass Typew,class Typep friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); private: bbnode * parent; //指向父节点的指针 bool LChild; //左儿子节点标识 }; templateclass Typew,class Typep class HeapNode { friend KnapTypew,Typep; public: operator Typep() const { return uprofit; } private: Typep uprofit, //节点的价值上界 profit; //节点所相应的价值 Typew weight; //节点所相应的重量 int level; //活节点在子集树中所处的层序号 bbnode *ptr; //指向活节点在子集中相应节点的指针 }; templateclass Typew,class Typep class Knap { templateclass Typew,class Typep friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); public: Typep MaxKnapsack(); private: MaxHeapHea