算法第六章.ppt

0/1背包问题DKP算法的实现 可用两个一维数组P和W来存放所有的序偶(Pl ,Wl) 序偶集S0,S1,…,Sn-1互相邻接的存放 各个集合用指针F[i]来指示, 0≤i≤n, F[i]指示S中的第一个元素所在的位置 S0 ={(0,0)} S1 ={(0,0),(1,2)} S2 ={(0,0),(1,2),(2,3),(3,5)} 1 2 3 4 5 6 7 8 0 0 1 0 1 2 3 0 0 2 0 2 3 5 P W F[0] F[1] F[3] F[2] 在生成Si1的过程中, 同时将Si-1和Si1按支配规则进行归并而生成Si , 因此不需要附加空间存放Si1 在Si-1中序偶是按P和W的递增次序排列的, 因此Si的序偶也按这种次序生成 procedure DKNAP(p,w,n,M,m) F[0]=1; P[1]=W[1]=0; l=h=1; F[1]=next=2; for i=1 to n-1 do { k=l ; u=r ; r是在l≤r≤h中,使得W[r]+wi≤M最大 for j=l to u do { (pp,ww)=(P[j]+pi,W[j]+wi) while ( k≤h and W[k]ww ) do ｛ P[next]=P[k]; W[next]=W[k]; next++; k++; } if ( k≤h and W[k]==ww) { pp=max{pp,P[k]} ; k++;} if ( ppP[next-1] ) {(P[next],W[next])=(pp,ww); next++;} while ( k≤h and P[k]≤P[next-1] ) do { k++; } } //end for while k≤h do { (P[next)],W[next])=(P[k],W[k]); next++; k++; } l=h+1; h=next-1; F[i+1]=next; } //end for call PARTS //算法DKP的6—11行 end DKNAP 计算S1到Sn-1 //要加代码才能实现 //将(pi,wi)加到Si-1中的序偶上 //将Si-1中的序偶并入Si中 //将Si-1中剩余的序偶并入Si中 // l和h分别指向Si的首端和末端 F[i+1]指向Si+1的第一个元素 Si-1和Si1按支配规则进行归并, 生成Si 第四章 动态规划4.6 可靠性设计 问题提出 可靠性设计 思路： 动态规划解法递推公式（4.17 4.18） 解法： 仿照0/1背包 6.6 可靠性设计 6.7 货郎担问题 问题描述: 某售货员要到若干个村庄售货, 各村庄之间的路程是己知的, 为了提高效率, 售货员决定从所在商店出发，到每个村庄售货一次, 然后返回商店, 问他应选择一条什么路线才能使所走的总路程最短? 设G(V,E)是一个具有边成本cij的有向图, G的一条周游路线是包含V中每个结点的一个有向环, 周游路线的成本是此路线上所有边的成本之和。 货郎担问题就是求取具有最小成本的周游路线问题。 1 4 3 2 15 6 8 20 12 9 9 13 5 10 10 8 假设周游路线是开始于结点1并终止于结点1的一条简单路径。 每一条周游路线都是由一条边1, k和一条由结点k到结点1的路径所组成的, 其中k∈V-{1}; 这条由结点k到结点1的路径通过V-{1,k}的每个结点各一次 最优性原理对货郎担问题成立 如果这条周游路线是最优的, 则这条由k到1的路径必定是通过V-{1,k}中所有结点的由k到1的最短路径, 因此最优性原理成立 1 4 3 2 15 6 8 20 12 9 9 13 5 10 10 8 设g(i,S)是由结点i开始, 通过S中的所有结点, 在结点1终止的一条最段路径长度 2≤k≤n g(1,V-{1})是一条最优的周游路线长度 于是可以得到: g(1,V-{1})=min{c1k+g(k,V-{1,k})} j∈S 上式一般化可得: g(i,S)=min{cij +g(j,V-{j})} 1 2 3 4 1 0 10 15 20 2 5 0 9 10 3 6 13 0 12 4 8 8 9 0 1 4 3 2 15 6 8 20 12 9 9 13 5 10 10 8 g(2,?)=c21=5 g(3,?)=c31=6 g(4,?)=c41=8 g(2,{3})=c23+g(3,?)=9+6=15 g(2,{4})=c24+g(4,?)=10+8=