資源背包動態(tài)規(guī)劃ppt課件(參考版)
2025-05-06 18:27本頁面
【正文】 ? 狀態(tài)轉(zhuǎn)移方程一般可寫成 : fi(j) = min{ fi1 ( k) + ui (j,k)} 。 ? 其中 X,Y計算如下， 進(jìn)行枚舉，對于所有 ji}},),(,{{1CjinfBjAiM INM A XYWiXni?? ??總結(jié) ? 對于資源類動態(tài)規(guī)劃問題，我們可以看出，問題描述必須有一個基本要素：資源，有時這種資源可能是金錢、空間或者時間，問題就是要對這些資源如何分配，一種基本的想法是將資源應(yīng)用于前 i個階段，然后考慮第 i個階段和前 i1個階段之間的關(guān)系。 說明 ? 利用前兩個優(yōu)化基本可以出解 ? 第 3個優(yōu)化，對每條流水線進(jìn)行動態(tài)規(guī)劃的剩余時間多少比較難確定，否則正確性難以保證，剩余時間越多，正確率越高，速度越慢。 2. 淘汰一些沒有意義狀態(tài)，比如生產(chǎn)了過多第三種物質(zhì)，卻沒把前兩種生產(chǎn)滿。(1*)39。(1*)39。 ? 如果前 x1條流水線只要生產(chǎn) i’漢堡， j’個薯條，生產(chǎn)的飲料為 f(x1,i’,j’) ? 因此有第 x條流水線必須生產(chǎn)了 ii’個漢堡， jj’個薯條，剩下的時間生產(chǎn) k個飲料。 分析 ? 對于每條流水線，它的生產(chǎn)時間是一定的，我們?nèi)绻懒松a(chǎn)漢堡和薯條的個數(shù)，就很容易計算出生產(chǎn)飲料的個數(shù)。求系統(tǒng)可能的最高可靠性。 思考題 3：系統(tǒng)可靠性 ? 一個系統(tǒng)由若干部件串聯(lián)而成 ， 只要有一個部件故障 ， 系統(tǒng)就不能正常運(yùn)行 ， 為提高系統(tǒng)的可靠性 ， 每一部件都裝有備用件 ， 一旦原部件故障 ，備用件就自動進(jìn)入系統(tǒng) 。 ?A[j]表示其中 第 j種錢幣的面值。 ?N=500,T=10000. 分析 ?設(shè) F[i]表示需要找的錢數(shù)為 i時所需要的最少錢幣數(shù)。 則狀態(tài)轉(zhuǎn)移方程為 : ? f(i,j) =Max{f[i1， k] + a[i， jj]} (1=i=N,1=j=M,0=k=j ) ? 初始值 : f(0,0)=0 ? 時間復(fù)雜度 O(N*M2) 思考題 2：硬幣找零 ?給定 N枚硬幣 ?給定 T元錢 ?用這 N枚硬幣找這 T元錢，使得剩下的錢最少。 ? 若公司 i獲得 j臺設(shè)備 ， 則能產(chǎn)生 Aij效益 ? 問如何分配設(shè)備使得總效益最大 ？ ? M=15， N=10。程序如下： for i:=1 to n do // 動態(tài)規(guī)劃，遞推求 f for j:=0 to m do begin if j=w[i] then //背包容量夠大 f[j]:=max(f
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1