資源背包動態(tài)規(guī)劃ppt課件-免費閱讀
【正文】 下圖是對第 3個優(yōu)化的說明： 總結 ? 第 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條流水線生產的飲料 = 前 x1條流水線生產的飲料 + 第 x條流水線生產的飲料 ? 所以有， f(x,i,j)=max{f(x1,i’,j’)+k} 32*)39。 ?時間復雜度為 O(N*T)。 思考題 1：機器分配 ? M臺設備 ， 分給 N個公司 。這樣對于某種物品要選取多個，都可以由若干個 2k個物品進行組合 (即 2進制數(shù) )。 ? F(i,j)=max{ f(i1,jk*w[i]) + k*c[i] } ? 0=k*w[i]=j 完全背包問題 ? 有 N件物品 。 ? 第 i件物品 Wi公斤 。 for i:=1 to n do // 動態(tài)規(guī)劃，遞推求 f for j:=1 to m do begin if j=w[i] then //背包容量夠大 f[i,j]:=max(f[i1,jw[i]]+c[i],f[i1,j]) else //背包容量不足 f[i,j]:=f[i1,j]。背包類動態(tài)規(guī)劃問題 長沙市雅禮中學 朱全民 經典的背包問題（ 01背包） ? 有 N件物品 。 end。 ? 第 i件物品價值 Ci元 。 ? 第 i件物品 Wi公斤 。例如第 i種物品要選 10個，則 10=23+21 。 ? 若公司 i獲得 j臺設備 ， 則能產生 Aij效益 ? 問如何分配設備使得總效益最大 ？ ? M=15， N=10。 思考題 3：系統(tǒng)可靠性 ? 一個系統(tǒng)由若干部件串聯(lián)而成 ， 只要有一個部件故障 ， 系統(tǒng)就不能正常運行 ， 為提高系統(tǒng)的可靠性 ， 每一部件都裝有備用件 ， 一旦原部件故障 ，備用件就自動進入系統(tǒng) 。(1*)39。 ? 其中 X,Y計算如下， 進行枚舉，對于所有 ji}},),(,{{1CjinfBjAiM INM A XYWiXni?? ??總結 ? 對于資源類動態(tài)規(guī)劃問題，我們可以看出，問題描述必須有一個基本要素：資源，有時這種資源可能是金錢、空間或者時間，問題就是要對這
教學課件相關推薦
鄂ICP備17016276號-1