第9章 第4节 动态规划经典题(c++版)

《第9章 第4节 动态规划经典题(c++版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章动态规划第一节动态规划的基本模型第二节动态规划与递推第三节背包问题第四节动态规划经典题动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处

2、理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。第四节动态规划经典题【例9-18】、合并石子【问题描述】在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。【编程任务】试设计一个程序，计算出将Ｎ堆石子合并成一堆的最小得分。【输入格式】第一行为一个正整数N(2≤Ｎ≤100)；以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(

3、1≤i≤N)。【输出格式】为一个正整数，即最小得分。s[i]表示前i堆石头的价值总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最优值。for(i=n;i>=1;i--)for(j=i+1;j<=n;j++)for(k=I;k<=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);输出F[1][n]【输入样例】713781621418【输出样例】239【参考程序】#include#includeintmin(inta,

4、intb){returna>b?b:a;//三目运算符，相当于if(a>b)returnb;elsereturna;}intf[101][101];ints[101];intn,i,j,k,x;intmain(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);s[i]=s[i-1]+x;}memset(f,127/3,sizeof(f));//赋值127是很大的正数，若无/3后面的相加for(i=1;i<=n;i++)f[i][i]=0;//可能超出int的范围for(i=n-

5、1;i>=1;i--)for(j=i+1;j<=n;j++)for(k=i;k<=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);printf("%d",f[1][n]);return0;}【例9-19】乘积最大【问题描述】今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出

6、了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62这时，符合题目要求的结果是：31*2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。【输入格式】mul.in第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）第二行是一个长度为N的数字串。【输出格式】mul.out输出所求得

7、的最大乘积（一个自然数）。【输入样例】421231【输出样例】62【算法分析】此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i][k]表示在前i位数中插入K个乘号所得的最大值，a[j][i]表示从第j位到第i位所组成的自然数。用f[i][k]存储阶段K的每一个状态，可以得状态转移方程：f[i][k]=max{f[j][k-1]*a[j+1][i]}（k<=j<=i）边界值：f[j][0]=a[1][j](1

8、态规划程序：For(k=1;k<=r;k++)//r为乘号个数for(i=k+1;i<=n;i++)for(j=k;j<=I;j++)if(f[i][k]