動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最佳加法表達(dá)式求最小值

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

2、字符中插入j個(gè)加號(hào)能達(dá)到的最小 值，那么最后的答案也即flength(s)m。于是，有DP方程：fij=min(fij,fkj-1+numk+1:i),numk+1:i表示k+1位到i位所形成的數(shù)字，這是把加號(hào)插入 第k+1個(gè)位置上。以下是給定整數(shù)串和加號(hào)個(gè)數(shù)的C語(yǔ)言程序：#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);以下是可以自己輸入整數(shù)串和加號(hào)個(gè)數(shù)的C語(yǔ)言程序：#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+)給二維數(shù)組num賦值,num表示整數(shù)串第i到j(luò)位(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(請(qǐng)輸入整數(shù)串：)；scanf(s,&ar