資源背包動態(tài)規(guī)劃ppt課件-文庫吧在線文庫
【正文】 價 Ck，以及當用 Mk個此備用件時部件的正常工作概率 Pk（ Mk），總費用上限 C。(ppjjpiiTxk ?????流水線資源分配圖 32*)39。 ? 設(shè)前 i個點的消耗 j的資源得到的最優(yōu)值，研究前 i1個點消耗的資源的最優(yōu)值，利用第 i個點決策轉(zhuǎn)移，如下圖。 3. 讓每條流水線大多數(shù)時間按成套時間生產(chǎn)，留下一些時間進行動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，極大地減少每種物品的產(chǎn)量從而極大地減少動態(tài)規(guī)劃的狀態(tài)數(shù)。因此， ? 假設(shè)第 i條流水線生產(chǎn)了 i’個漢堡， j’個薯條 ,那么還能生產(chǎn)飲料個數(shù)為： k’=(Tii’*p1j’*p2)/p3 動態(tài)規(guī)劃 ? 設(shè) f(x,i,j)表示前 x條流水線生產(chǎn) i個漢堡， j個薯條最多還能生產(chǎn)飲料個數(shù)。顯然有： ?F[i]=Min{F[ i A[j] ] + 1} { i≤ T， 1≤j≤N} ?初始值： F[0]=0。 在這里為了使得每個物品只取 1個或不取 ,采用了每次取 j都是與 i1進行比較，實際上保存了每 1步取不同 j的值 改進程序 ? 事實上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心 f(j),因此，在對 f(j)更新時，只要背包容量可以，那么可以反復(fù)更新。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的 j換成物美價廉的 i,得到至少不會更差的方案。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 問選取裝載哪些物品，使得卡車開車正好裝滿時，運送的總價值最大？ 若無法裝滿卡車，則輸出無解。 ? 按每種物品進行搜索，方法如下： – 對第 i種物品進行搜索 – 如果所有的物品都搜索完，則更新最優(yōu)解 – 如果當前的估計達不到最優(yōu)解，則回溯 – 如果第 i種物品能放，則放，并標記，否則選下一個物品 – 清除標記 – 回溯 動態(tài)規(guī)劃 ? 可以按每個物品進行規(guī)劃，同樣每種物品有選和不選兩種選擇 ? 設(shè) F(i,j)表示前 i件物品載重為 j的最大效益，則有 ? 1=i=N, 0=j=N ? 初值： F(0,j)=0 ? F(N,M)即答案 ? 顯然時間復(fù)雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFMa xjiF),1(],[])[,1(),(主程序如下 for i:=1 to m do f[0,i]:=0。 ? 第 i件物品價值 Ci元 。 ? 第 i件物品 Wi公斤 。 ? 問選取裝載哪些物品，使得卡車運送的總價值最大？ 分析 ? 假設(shè)只有主件的情況 ，顯然與經(jīng)典背包問題完
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1