回溯算法解决背包问题_源代码.doc

templateclass Knap/建立类knapfriend Typew Knapsack(Typew* ，Typew*，Typew，int );/友元函数的声明private:/私有成员声明 Typew Bound(int i); void Backtrack(int i); Typew c;/背包容量 int n; /物品数 Typew *w;/物品重量数组 Typew *p;/物品价值数组 Typew cw;/当前重量 Typew cp;/当前价值 Typew bestp;/当前最优值 ;第二段templatevoid Knap:Backtrack(int i)/友元函数的定义 if(in)/到达叶结点 bestp=cp;return; if(cw+wibestp)/搜索右子树 Backtrack(i+1); 第三段（重要）templateTypep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) b += pi/wi * cleft; return b;第四段class Object friend int Knapsack(int *,int *,int ,int );public: int operator=a.d); private: int ID;/对象好 float d;/收益密度;第五段：templateTypew, Knapsack(tTypew,p,Typew, w,Typew,c,int n)/为Knap:Backtrack初始化 Typew, W=0; Typew, P=0; Object *Q=new Objectn; for(int i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/装入所有物品 /依物品单位重量排序 Sort（Q，n); KnapK K.p = new Typepn+1; K.w = new Typepn+1; K.x = new Typepn+1; for( i=1;i=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); delete Q; delete K.w; delete K.p; return K.bestp;补充void main() int *p; int *w; int c=0; int n=0; int i=0; cout请输入背包个数：n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout请输入背包容量：c; cout请依此输入每个物品的重量：endl; for(i=1;iwi; cout请依此