動態(tài)規(guī)劃實現最佳加法表達式求最小值

1、實驗習題：最佳加法表達式C語言實現有一個由1.9組成的數字串，問如果將m個加號插入到這個數字 串中，使得所形成的算術表達式的值最小添加加號后，表達式的最后一定是個數字串，我們發(fā)現：把以前狀態(tài)認為是在前i個字符中插入m-1個加號(i當作決策 在枚舉)，然后i+1到最后一位一定是整個沒被分割的數字串，第m 個加號就添加在i與i+1個數字之間。即構造出了整個數字串的最優(yōu) 解。至于前i個字符中插入m-1個加號，這又回到原問題的形式，回 到以前狀態(tài)，那么狀態(tài)轉移方程可構造。例：數字串79846,若需要加入兩個加號，則最佳方案為 79+8+46，算術表達式的值為133。算法實現分析：用fij，表示在前i個

2、字符中插入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 100000void DP(int *a, int t, int m)(int i,j,d,k,min;int fmt;int nummm;for(i=0;i j) numij=INF;else(d=d*10 + aj;numij = d

3、; 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 100000void DP(char *a, i

4、nt 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,&ar