第四章基本的算法策略.pptVIP

4.4 贪婪算法 4.4.1 可绝对贪婪问题 4.4.2 相对或近似贪婪问题 4.4.3 关于贪婪策略讨论 4.5 动态规划 4.5.1 认识动态规划 4.5.2 算法框架 4.5.3 突出阶段性的动态规划应用 4.5.4 突出递推的动态规划应用 4.6 算法策略间的比较 4.6.1 不同算法策略特点小结 4.6.2 算法策略间的关联 【例2】资源分配问题。 设有资源a,分配给n个项目,gi(x)为第i个项目分得资源x所得到的利润。求总利润最大的资源分配方案，也就是解下列问题： max z=g1(x1)+ g2(x2)+……gn(xn) x1+xx2+x3+……xn=a, xi≥0,i=1，2,3,……,n 函数gi(x)以数据表的形式给出. 例如：现有7万元投资到A，B，C 三个项目，利润见表,求问题总利润最大的资源分配方案。 上节 下节 算法设计 1．阶段划分及决策 比较直观的阶段划分就是逐步考虑每一个项目在不 同投资额下的利润情况。 3. 数据结构设计： 1) 开辟一维数组q来存储原始数据。 2) 另开辟一维数组f存储当前最大收益情况。 3) 开辟记录中间结果的一维数组数组temp，记录正在计 算的最大收益。 4) 开辟二维数组a。 5) 数组gain存储第i个工程投资数的最后结果。 上节 下节 对于一般问题设计算法如下： main( )  { int i,j,k,m,n,rest; int a[100][100]，gain[100]; float q[100],f[100],temp[100]; print(“How mang item? ”); input (m); print(“How mang money? ”); input (n); print(“input gain table:”); for( j=0;j= n;j++) { input(q[j]); f[j]=q[j];} for( j=0;j= n;j++) a[1,j]=j; 上节 下节 for( k=2;k=m;k++) { for( j=0;j= n;j++) { temp[j]=q[j]; input(q[j]); a[k][j]=0;} for( j=0 ;j= n;j++) 　 for( i=0 ;i=j;i++) if（f[j-i]+q[i]temp[j]） { temp[j]=f[j-i]+q[i]; a[k,j]=i; } for(j=0;j= n;j++) f[j]=temp[j]; } rest=n; for(i=m;i=1;i--) { gain[i]=a[i][rest]; rest=rest-gain[i];} for(i=1;i=m;i++) print(gain[i],” ”); print(f[n]); } 【例3】n个矩阵连乘的问题。 问题分析 算法设计 算法1(递归算法) 算法1说明 算法2(递归算法) 算法3(非递归算法) 输出算法 上节 下节 问题分析 多个矩阵连乘运算是满足结合律的。 例: M1[5*20] * M2[20*50] * M3[50*1] * M4[1*100]分别按 ((M1*M2)*M3)*M4，M1*(M2*(M3*M4))，(M1*(M2*M3))*M4 的次序相乘,各需进行 5750, 115000, 1600次乘法。 这个问题要用“动态规划”算法来完成: 首先,从两个矩阵相乘的情况开始； 然后,尝试三个矩阵相乘的情况； …… 最后,等到n个矩阵相乘所用的最少的乘法次数及结合方式。 上节 下节 算法设计