[工学]chapter 5 动态规划法.ppt

算法：Allocate 输入：资源总数m，工程项目数n，以及G(i,j)：对工程i投资j的利润 输出：数组X[1..n]，其中X[i]是分配给工程i的投资数。M是总利润 方法：F[i,j]记录的是fi(j)的最大利润。P[i,j]记录的是使fi(j)最大时分配的资源数。 5.4 资源分配问题 procedure Allocate begin for i=0 to m do // 资源m，工程n { F[1,i]=G[1,i]; //对工程1投资i时的利润 P[1,i]=i;} //利润最大时的投资数 M[1]=max{F[1,0], F[1,1],…F[1,m]}; Q[1]=k; //k是使M[1]取最大值时的F[1,k]中的下标 for i=2 to n do { F[i,0]=G[i,0]+F[i-1,0]; P[i,0]=0; for j=1 to m do //寻找给第i项工程的投资数 { 设k是使得G[i,k]+F[i-1,j-k]取最大值的下标 F[i,j]=G[i,k]+F[i-1,j-k]; P[i,j]=k; } 5.4 资源分配问题 0 1 2 3 4 5 6 1 0 1.2 1.5 1.85 2.4 2.8 3.3 2 3 x1 0 1 2 3 4 5 6 GA(x1) 0 1.2 1.5 1.85 2.4 2.8 3.3 GB(x1) 0 1.8 2.0 2.25 2.4 2.5 2.6 GC(x1) 0 1.3 1.9 2.2 2.45 2.7 3.0 5.4 资源分配问题 F[i,j] 给前i项工程投资j的最大利润 0 1 2 3 4 5 6 1 0 1 2 3 4 5 6 2 3 P[i,j] 使F[i,j]最大时给第i项工程分配的资源数 1 2 3 3.3 M： 1 2 3 6 Q： 0 1 2 3 4 5 6 1 0 1.2 1.5 1.85 2.4 2.8 3.3 2 0 1.8 3.0 3.3 3.65 4.2 4.6 3 0 1.8 3.1 4.3 4.9 5.2 5.55 x1 0 1 2 3 4 5 6 GA(x1) 0 1.2 1.5 1.85 2.4 2.8 3.3 GB(x1) 0 1.8 2.0 2.25 2.4 2.5 2.6 GC(x1) 0 1.3 1.9 2.2 2.45 2.7 3.0 5.4 资源分配问题 F[i,j] 给前i项工程投资j的最大利润 0 1 2 3 4 5 6 1 0 1 2 3 4 5 6 2 0 1 1 1 1 1 1 3 0 0 1 1,0 2 3,2 2 P[i,j] 使F[i,j]最大时给第i项工程分配的资源数 1 2 3 3.3 4.6 5.55 M： 1 2 3 6 6 6 Q： procedure Allocate (续) begin for i=2 to n do { F[i,0]=G[i,0]+F[i-1,0]; P[i,0]=0; for j=1 to m do //寻找给第i项工程的投资数 { 设k是使得G[i,k]+F[i-1,j-k]取最大值的下标 F[i,j]=G[i,k]+F[i-1,j-k]; P[i,j]=k; } M[i]=max{F[i,0],F[i,1],…F[i,m]}; Q[i]=r; //r是使M[i]取最大值的F[i,r]的下标 } M=max{M[1],M[2]..M[n]}; //最大总利润 5.4 资源分配问题 procedure Allocate （续） begin M=max{M[1],M[2]..M[n]}; //最大总利润 设s是使M取最大值的M[s]的下标 if sn then for i=s+1 to n do x[i]=0 ; //后面的工程分配资源数为0 x[s]=P[s,Q[s]]; //分配给第s项工程的投资数 j=m-x[s]; for i=s-1 to 1 do { x[i]=P[i,j]; j=j-x[i]; } end 5.4 资源分配问题 算法在Θ(m2n)的时间内找到最佳资源分配方案 0 1 2 3 4