?一、例題要求及理論分析

聲明：理論指導(dǎo)《算法設(shè)計(jì)與分析 第四版》

因?yàn)檫@個(gè)地方用到了三維數(shù)組，感覺很有意思就故意挑出來(lái)分享給大家（三維數(shù)組可以看成很多頁(yè)二維數(shù)組）

4.5.1認(rèn)識(shí)動(dòng)態(tài)規(guī)劃
數(shù)塔問(wèn)題：
如圖4-12所示的一個(gè)數(shù)塔，從頂層到底層或從底層到頂層，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，要求找出一條路徑，使路徑上的數(shù)值和最大。
問(wèn)題分析：
(1）不難理解，這個(gè)問(wèn)題用貪婪算法有可能會(huì)找不到真正的最大和。以圖4-12為例就是如此。采用貪婪策略，無(wú)論是自上面下，還是自下而上，每次向下都選擇較大的一個(gè)數(shù)移動(dòng)，則路徑和分別為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?數(shù)塔圖
9+15+8+9+10=51（自上而下）,19+2+10+12+9=52（自下而上）
都得不到最優(yōu)解，真正的最和是：
9+12+10+18+10=59
(2）要找到最大和的前提條件是，要能看到數(shù)塔的全貌，下面的算法設(shè)計(jì)都是以此為前提的。
在知道數(shù)塔全貌的前提下，可以用枚舉法或第5章將學(xué)習(xí)的搜索算法來(lái)解決問(wèn)題。但從圖中可以看出，在數(shù)塔層數(shù)為?n?時(shí)，要枚舉的路徑為2^(n-1)條。在?n?稍大的情況下，需要列舉出的路徑條數(shù)是一個(gè)非常龐大的數(shù)目。所以枚舉法也不是一個(gè)適合此問(wèn)題的算法策略。
(3）這個(gè)問(wèn)題的原始數(shù)據(jù)是一個(gè)三角形的二維圖形，而且問(wèn)題的答案與各層數(shù)據(jù)間關(guān)系復(fù)雜，不適合用分治算法分解為與原問(wèn)題相似的子問(wèn)題。
下面就學(xué)習(xí)用動(dòng)態(tài)規(guī)劃解決此問(wèn)題。
算法設(shè)計(jì)：動(dòng)態(tài)規(guī)劃設(shè)計(jì)過(guò)程如下。
1．階段劃分
從數(shù)塔問(wèn)題的特點(diǎn)來(lái)看，不難發(fā)現(xiàn)解決問(wèn)題的階段劃分，應(yīng)該是自下而上逐層決策。不同于貪婪策略的是做出的不是唯一決策，第一步對(duì)于第五層的8個(gè)數(shù)據(jù)，做如下4次決策：
對(duì)經(jīng)過(guò)第四層2的路徑，在第五層的19,7中選擇19;
對(duì)經(jīng)過(guò)第四層18的路徑，在第五層的7,10中選擇10;
對(duì)經(jīng)過(guò)第四層9的路徑，在第五層的10,4中也選擇10;
對(duì)經(jīng)過(guò)第四層5的路徑，在第五層的4,16中選擇16。
這是一次決策過(guò)程，也是一次遞推過(guò)程和降階過(guò)程。因?yàn)橐陨系臎Q策結(jié)果將5階數(shù)塔題變?yōu)?階子問(wèn)題，遞推出第四層與第五層的和為：
21(2+19),28(18+10),19(9+10),21(5+16)

用同樣的方法還可以將4階數(shù)塔問(wèn)題變?yōu)?階數(shù)塔問(wèn)題……最后得到的1階數(shù)問(wèn)題，就是整個(gè)問(wèn)題的最優(yōu)解。
2、存儲(chǔ)、求解
1）原始信息存儲(chǔ)
原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型變量 n 存儲(chǔ)，數(shù)塔中的數(shù)據(jù)用二維數(shù)組 data ，存儲(chǔ)成如下的下三角陣：

9

12 15

10? 6? ?8

2? ?18? 9? 5

19? 7? 10? 4? 16

2）動(dòng)態(tài)規(guī)劃過(guò)程存儲(chǔ)
由于早期階段動(dòng)態(tài)規(guī)劃決策的結(jié)果是一組數(shù)據(jù)，且本次的決策結(jié)果是下次決策的唯一依據(jù)（無(wú)后效性），所以必須在存儲(chǔ)每一次決策的結(jié)果，若僅僅是求最優(yōu)解，用一個(gè)一維數(shù)組存儲(chǔ)最新的決策結(jié)果即可；但若要同時(shí)找出最優(yōu)解的構(gòu)成或路徑，則必須用二維數(shù)組 d 存儲(chǔ)各階段的決策結(jié)果。根據(jù)上面的算法設(shè)計(jì)，二維數(shù)組 d 的存儲(chǔ)內(nèi)容如下：

?d [ n ][j]= data [ n ][j]? ? j=1,2,……，n;
?i = n -1, n -2,…,1, j =1,2,…, i 時(shí)
?d [ i ][ j ]= max ( d [ i +1][j], d [ i +1][j+1])+ data [ i ][j]
最后 d [1][1］存儲(chǔ)的就是問(wèn)題的結(jié)果。

二、代碼

#include<stdio.h>
int main()
{
 int a [50][50][3], i , j , n ;
 printf (" please input the number of rows :\n");
 scanf("%d",&n);
 for ( i =1; i <= n ; i = i +1)
   for ( j =1; j <= i ; j = j +1)
    { 
        scanf("%d",&a [ i ][ j ][1]);
        a [ i ][ j ][2]= a [ i ][ j ][1];
        a [ i ][ j ][3]=0;
    }
 for ( i = n -1; i >=1; i = i -1)
   for ( j =1; j <= i ; j = j +1)
    if ( a [ i +1][ j ][2]> a [ i +1][ j +1][2])
        {
        a [ i ][ j ][2]= a [ i ][ j ][2]+ a [ i +1][ j ][2];
        a [ i ][ j ][3]=0;
        }
   else 
       {
       a [ i ][ j ][2]= a [ i ][ j ][2]+ a [ i +1][ j +1][2]; a [ i ][ j ][3]=1;
       }
   printf (" max =%d\n", a [1][1][2]);
    j =1;
for ( i =1; i <= n -1; i = i +1)
{ printf ( "%d->",a [ i ][ j ][1]);
 j = j + a [ i ][ j ][3];
}
 printf ("%d", a [ n ][ i ][1]);
 return 0;
}

三、運(yùn)行結(jié)果?

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-777603.html

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——數(shù)塔問(wèn)題（三維數(shù)組的應(yīng)用）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！