算法设计与分析：第7章 动态规划法.pptVIP

程序7-80/1背包的递归算法classKnapsack{public:Knapsack(intmSize,floatcap,float*wei,T*prof);//构造函数 //用于给n,m,w,p赋值TRKnap();private:Tf(intj,floatX);floatm; //背包载重intn; //物品个数float*w; //物品重量T*p; //物品价值}templateclassTTKnapsackT::f(intj,floatX) //私有递归函数{ //物品0-j放入载重X的背包中的最大收益if(j0)return((x0)?-INFTY:0);if(Xw[j])returnf(j-1,X);//只有一种选择——不取物品jelse{ Ta=f(j-1,X); Tb=f(j-1,X-w[j])+p[j];//两种选择——取或不取物品j if(ab)returna; elsereturnb;//取其中较大的一种选择 }}templateclassTTKnapsackT::RKnap() //公有函数{if(n0)returnf(n-1,m);elsereturnNoAns;//一个代表无收益的常量}例7-8有0/1背包问题n=3，(w0,w1,w2)=(2,3,4)，(p0,p1,p2)=(1,2,4)，M=6，求最优解值f(2,6)。递归求解过程：f(2,6)=max{f(1,6),f(1,6-4)+4}=f(1,6)=max{f(0,6),f(0,6-3)+2}=f(1,2)=f(0,2)=f(0,6)=max{f(-1,6),f(-1,6-2)+1}=f(0,3)=max{f(-1,3),f(-1,3-2)+1}=f(0,2)=max{f(-1,2),f(-1,2-2)+1}=111135∵f(-1,y)=0，y≥0templateclassTvoidExtLGraphT::Earliest(int*earliest,int*order)//求各顶点的earliest[i]{for(inti=0;in;i++)earliest[i]=0;for(i=0;in;i++) //从前向后{//前提：图的拓扑排序结果已存在于order数组中intk=order[i];for(ENodeT*p=a[k];p;p=p-nextArc)if(earliest[p-adjVex]earliest[k]+p-w) earliest[p-adjVex]=earliest[k]+p-w; //更新k的所有后继结点的earliest[]值}}templateclassTvoidExtLGraphT::Latest(int*latest,int*order,intlongest)//求各顶点的latest[i]{ for(inti=0;in;i++)latest[i]=longest;for(i=n-2;i-1;i--) //从后向前{ //图的拓扑排序结果已存在于order数组中intj=order[i];for(ENodeT*p=a[j];p;p=p-nextArc) if(latest[j]latest[p-adjVex]-p-w) latest[j]=latest[p-adjVex]-p-w; //更新j的latest[]值}}性能分析关键路径算法与拓扑排序有相同的时间复杂度，其时间复杂度为O(n+e)。课堂练习：求下图中的关键路径和关键活动8765342105413322634142012345678earliest(i)025457111014latest(i)0364571110140,3,3,4,3,5,4,6,5,7,6,8,7,8是关键活动.因此关键路径有(0,3,4,6,8)和(0,3,5,7,8),长度为