a[i][j]=a[i][j-1]+r[i][j-1]; printf(\
所求左上角顶点到右下角顶点的最大路程即最优值为a(n,m)。
6-4 求解边数值三角形的最短路径
已知边数值三角形每两点间距离如图7-4所示，每一个点可向左或向右两个去向，求三角形顶点到底边的最短路径。
图7-4 三角形边数值数据
1) 算法设计
设边数值三角形为n行(不包含作为边终止点的三角形底边)，每点为(i，j)，i=1,2,……，n；j=1,2,……，i.从点(i,j)向左的边长记为l(i,j)，点(i,j)向右的边长记为r(i,j)。记a(i,j)为点（i,j）到底边的最短路程。显然
a(i,j)=min(a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j)) st(i,j)={‘l’,’r’}
应用逆推求解，所求的顶点A到底边的最短路程为a(1,1). 2) 边数值三角形最短路径搜索C程序设计 // 边数值三角形最短路径搜索 #include \#include
void main()
{ int n,i,j,t,s;
int a[50][50],l[50][50],r[50][50];char st[50][50];
t=time()00;srand(t); // 随机数发生器初始化 printf(\请输入数字三角形的行数n:\ scanf(\
for(i=1;i {for(j=1;j<=37-4*i;j++) printf(\ for(j=1;j<=i;j++) printf(\ for(j=1;j<=36-4*i;j++) printf(\ for(j=1;j<=i;j++) {l[i][j]=rand()/1000+1;printf(\ r[i][j]=rand()/1000+1;printf(\ printf(\ for(j=1;j<=37-4*(n+1);j++) printf(\ for(j=1;j<=n+1;j++) printf(\printf(\底边\\n\\n\ for(i=n;i>=1;i--) // 逆推求取最短路径 {for(j=1;j<=i;j++) if(a[i+1][j]+l[i][j] {a[i][j]=a[i+1][j+1]+r[i][j];st[i][j]='r';} } printf(\最短路程为：%d\printf(\最短路径为：顶点A \for(j=1,i=1;i<=n;i++) if(st[i][j]=='l') printf(\ else {printf(\printf(\底边。\} 6-5 求解点数值矩阵最小路径 随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。 1) 算法设计 应用动态规划，即从右下角逐行反推至左上角。确定n,m后，随机产生的整数二维数组a(n,m)作矩阵输出，同时赋给部分和数组b(n,m)。这里数组b(i,j)为点(i,j)到右下角的最小数值和，stm(i,j)是点(i,j)向右（R）或向下（D）或向右下（O）的路标字符数组。 注意到最后一行与最后一列各数只有一个出口,于是由b(n,m)?开始向左逐个推出同行的b(n,j),(j=m-1,...,2,1);向上逐个推出同列的b(i,m),(i=n-1,...,2,1)。 b(i,j)与stc(i,j)(i=n-1,...,2,1,j=m-1,...,2,1))的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定: 首先,作赋值 b(i,j)=yb+b(i+ 1, j + 1): stc(i, j) = \其中变量yb为原b(i,j)的值)。 然后,求 b(i+1,j) 与 b(i,j+1) 的最小值 min。 如果 b(i+1,j+1)>min ,说明前面为b(i,j)赋值不对,作修改: b(i,j)=yb+min 若min 为 b(i+1,j),则 stc(i,j)=\否则 stc(i,j)=\ 这样反推所得b(1,1)即为所求的最小路径数字和。 为了打印最小路径,利用c数组从上而下操作:先打印a(1,1),i=1,j=1. 若 stc(i,j)=\则j增1,即j=j+1,然后打印 \与右边整数a(i,j); 若 stc(i,j)=\则i增1,即i=i+1,然后打印 \与下面整数a(i,j); 若 stc(i,j)=\则i,j均增1,即i=i+1,j=j+1,然后打印 \与斜向右下整数a(i,j); 依此类推,直至打印到终点a(n,m)。 6-6 西瓜分堆 已知的n个西瓜的重量分别为整数，请把这堆西瓜分成两堆，每堆的个数不一定相等，使两堆西瓜重量之差为最小。 (1） 设计要点 两组数据之和不一定相等，不妨把较少的一堆称为第1堆。设n个整数b(i)之和为s，则第1堆数据之和s1≤[s/2]，这里[x]为x的取整。 问题要求在满足s1≤[s/2]前提下求s1最大值maxc，这样两堆数据和之差的最小值为mind=s-2*maxc。 为了求s1的最大值，应用动态规划设计，按分每一个瓜为一个阶段，共分为n个阶段。每一个阶段都面临两个决策：选与不选该瓜到第1组。 1） 建立递推关系 设m(i,j)为第1堆距离c1=[s/2]还差重量为j，可取瓜编号范围为：i,i+1,…,n的最大装载重量值。则 当0≤j 不装入西瓜i，这时最大重量值为m(i+1, j)； 装入西瓜i，这时已增加重量b(i)，剩余重量为j?b(i)，可以选择西瓜i+1,…,n来装，最大载重量值为m(i+1,j?b(i))+b(i)。我们期望的最大载重量值是两者中的最大者。于是有递推关系 0?j?b(i)?m(i?1,j)m(i,j)???max(m(i?1,j),m(i?1,j?b(i))?b(i)) j?b(i) 以上j与b(i)均为正整数，i=1,2,…,n, 所求最优值m(1,c1)即为s1的最大值maxc。因而得两组数据和之差的最小值为mind=s-2*maxc=s-2*m(1,c1)。 2） 递推计算最优值 for(j=0;j for(j=b(n);j<=c1;j++) m(n,j)=b(n); // 首先计算m(n,j) for(i=n-1;i>=1;i--) // 逆推计算m(i,j) for(j=0;j<=c1;j++) if(j>=b(i) && m(i+1,j) m(i,j)=m(i+1,j); printf(\3） 构造最优解 构造最优解即给出所得最优值时的分瓜方案。 if(m(i,cb)>m(i+1,cb)) （其中cb为当前的剩余量，i=1,2, n?1） 第1堆分b(i); else 不分b(i); if(m(1,c1)-sb=b(n)) 则第1堆分b(n)。 （2）求解两组数据和之差的最小值程序设计 // 求解两组数据和之差的最小值 #include {int n,c1,i,j,s,t,cb,sb,b[N],m[N][10*N]; printf(\ s=0; for(i=1;i<=n;i++) // 输入n个西瓜重量整数 {printf(\请输入第%d个整数：\ scanf(\ } c1=s/2; printf(\各个西瓜重量：\ for(i=1;i<=n;i++) printf(\ printf(\总重量s=%d \\n\ for(j=0;j m[n][j]=0; for(j=b[n];j<=c1;j++) m[n][j]=b[n]; // 首先计算m(n,j) for(i=n-1;i>=1;i--) // 逆推计算m(i,j) for(j=0;j<=c1;j++) if(j>=b[i] && m[i+1][j] else m[i][j]=m[i+1][j]; // 得最优值m(1,c1) printf(\两堆之差最小值为：%d \\n\printf(\第1堆: \ cb=m[1][c1]; for(sb=0,i=1;i<=n-1;i++) // 构造最优解，输出第1堆的西瓜 if(m[i][cb]>m[i+1][cb]) {cb-=b[i];sb+=b[i]; printf(\ b[i]=0; // b(i)分后赋0,为输出第2堆作准备 } if(m[1][c1]-sb==b[n]) {printf(\ sb+=b[n]; b[n]=0; } printf(\ printf(\第2堆: \ for(sb=0,i=1;i<=n;i++) // 输出第2堆西瓜 if(b[i]>0) {sb+=b[i]; printf(\ } printf(\} 6-7 应用递推实现动态规划求解序列的最小子段和 应用递推实现动态规划求解：给定n个整数（可能为负整数）组成的序列a1,a2,,an，求该序列形如?ak段和的最小值。 k?ij递推实现动态规划求解： 1） 动态规划算法设计 设q[j]为序列前j项之和的最小值，即 q[j]?min{?a[k]}1?i?jk?ij(1?j?n) 由q[j]的定义,得q[j]的递推关系: q[j?1]?a[j]q[j?1]?0 q[j]????a[j]q[j?1]?0(1?j?n) 初始条件： Q[0]=0 (没有项时，其值自然为0)。