動態(tài)規(guī)劃背包問題ppt課件-資料下載頁
2025-05-06 12:09本頁面
【正文】 1,i’,j’) ? 因此有第 x條流水線必須生產了 ii’個漢堡， jj’個薯條，剩下的時間生產 k個飲料。 ? 因為前 x條流水線生產的飲料 = 前 x1條流水線生產的飲料 + 第 x條流水線生產的飲料 ? 所以有， f(x,i,j)=max{f(x1,i’,j’)+k} 32*)39。(1*)39。(ppjjpiiTxk ?????26 流水線資源分配圖 32*)39。(1*)39。(ppjjpiiTxk ?????其中，27 思考？ ?f(x,i,j)=max{f(x1,i’,j’)+k} 1=x=n=10,0=i’=i=100, 0=j’=j=100 ?k可以實時求出 ?時間復雜度為 10*1002*1002=109 ?顯然超時！ 28 優(yōu)化 1. 求出最多可能生產多少套，減少不必要循環(huán)。 2. 淘汰一些沒有意義狀態(tài)，比如生產了過多第三種物質，卻沒把前兩種生產滿。 3. 讓每條流水線大多數(shù)時間按成套時間生產，留下一些時間進行動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，極大地減少每種物品的產量從而極大地減少動態(tài)規(guī)劃的狀態(tài)數(shù)。 29 說明 ? 利用前兩個優(yōu)化基本可以出解 ? 第 3個優(yōu)化，對每條流水線進行動態(tài)規(guī)劃的剩余時間多少比較難確定，否則正確性難以保證，剩余時間越多，正確率越高，速度越慢。下圖是對第 3個優(yōu)化的說明： 30 總結 ?第 1步：采用優(yōu)化方法 3，將每條流水線的 部分時間按成套生產，設第 i條流水線生產套餐 Wi套，剩下的時間為 Ti； ?第 2步，對每條流水線的剩下時間進行動態(tài)規(guī)劃 ,并采用優(yōu)化 1， 2； ?第 3步，求總套數(shù) = 貪心總套數(shù) X + 動態(tài)規(guī)劃的套數(shù) Y。 ?其中 X,Y計算如下， 進行枚舉，對于所有 ji}},),(,{{1CjinfBjAiMI NMA XYWiXni?? ??31 總結 ? 對于資源類動態(tài)規(guī)劃問題，我們可以看出，問題描述必須有一個基本要素：資源，有時這種資源可能是金錢、空間或者時間，問題就是要對這些資源如何分配，一種基本的想法是將資源應用于前 i個階段，然后考慮第 i個階段和前 i1個階段之間的關系。 ? 設前 i個點的消耗 j的資源得到的最優(yōu)值，研究前 i1個點消耗的資源的最優(yōu)值，利用第 i個點決策轉移，如下圖。 ? 狀態(tài)轉移方程一般可寫成 : fi(j) = min{ fi1 ( k) + ui (j,k)}
教學課件相關推薦
鄂ICP備17016276號-1