动态规划实现最佳加法表达式求最小值.doc

实验习题：最佳加法表达式C语言实现有一个由1.9组成的数字串,问如果将m个加号插入到这个数字串中，使得所形成的算术表达式的值最小添加加号后，表达式的最后一定是个数字串,我们发现：把以前状态认为是在前i个字符中插入m-1个加号（i当作决策在枚举），然后i+1到最后一位一定是整个没被分割的数字串，第m个加号就添加在i与i+1个数字之间。即构造出了整个数字串的最优解。至于前i个字符中插入m-1个加号，这又回到原问题的形式，回到以前状态，那么状态转移方程可构造。例：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值为133。算法实现分析：用fij，表示在前i个字符中插入j个加号能达到的最小值，那么最后的答案也即flength(s)m。于是，有DP方程：fij=min(fij,fkj-1+numk+1:i),numk+1:i 表示k+1位到i位所形成的数字，这是把加号插入第k+1个位置上。以下是给定整数串和加号个数的C语言程序：#include#include #define max 100#define INF 100000 void DP(int *a, int t, int m)int i,j,d,k,min;int fmt;int nummm; for(i=0;im;i+) /给二维数组num赋值,num表示整数串第i到j位 for(j=0,d=0;j j) numij=INF; else d=d*10 + aj; numij = d; for(i = 1; i= m; i+) for(j = 0; j =i) fij=INF; else if(j=0) fij=num0i-1; else for(min=INF,k=1;kfij)min=fij; fij=min; printf(最小值为：%d,fmt); int main()int m;int arrmax =7, 9, 8, 5, 3;int time=2;m = 5;DP(arr,time,m); 以下是可以自己输入整数串和加号个数的C语言程序：#include#include #define max 100#define INF 100000 void DP(char *a, int t, int m)int i,j,d,k,min;int fm+1t+1; int nummm; for(i=0;im;i+) /给二维数组num赋值,num表示整数串第i到j位 for(j=0,d=0;j j) numij=INF; else d=d*10 + (int)(aj-0); numij = d; for(i = 1; i= m; i+) for(j = 0; j =i) fij=INF; else if(j=0) fij=num0i-1; else for(min=INF,k=1;kfij)min=fij; fij=min; printf(最小值为：%d,fmt); int main()int m;int time;/int arrmax =7, 9, 8, 5, 3;char arrmax;printf(请输入整数串：);scanf(%s,&a