ascal動(dòng)態(tài)規(guī)劃ppt課件-資料下載頁
2025-05-05 08:07本頁面
【正文】 放入一個(gè)容量為 v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣： f[i][v]=max{f[i1][vk*c[i]]+k*w[i]} 0=k*c[i]=v [題 8] 攔截導(dǎo)彈 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來時(shí)候的高度。 樣例： INPUT 389 207 155 300 299 170 158 65 OUTPUT 6 （最多能攔截的導(dǎo)彈數(shù)） ， [題 8] 攔截導(dǎo)彈 【 分析 】 設(shè) D(i) 為第 i 枚導(dǎo)彈被攔截之后，這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)（包含被攔截的第 i 枚）。我們可以設(shè)想，當(dāng)系統(tǒng)攔截了第 k 枚導(dǎo)彈 x k ，而 x k 又是序列 X={x 1 ,x 2 ,…,x n } 中的最小值，即第 k 枚導(dǎo)彈為所有飛來的導(dǎo)彈中高度最低的，則有 D(k)=1 ；當(dāng)系統(tǒng)攔截了最后一枚導(dǎo)彈 xn ，那么，系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了，即 D(n)=1 ；其它情況下，也應(yīng)該有 D(i)≥1 。根據(jù)以上分析，可歸納出問題的動(dòng)態(tài)規(guī)劃遞歸方程為： 假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax （即問題的最優(yōu)值），則 dmax （ i 為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號(hào)） 習(xí)題 1. 7萬元投資到 A、 B、 C 3個(gè)項(xiàng)目，其利潤(rùn)見下表： 如何分配投資額，使獲得的利潤(rùn)最大。 2. 編寫用動(dòng)態(tài)規(guī)劃法求組合數(shù) 3. 有 n個(gè)整數(shù)排成一圈，現(xiàn)在要從中找出連續(xù)的一段數(shù)串，使得這串?dāng)?shù)的和最大。 mnC
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1