資源背包動態(tài)規(guī)劃ppt課件(存儲版)
【正文】 些資源如何分配，一種基本的想法是將資源應(yīng)用于前 i個階段，然后考慮第 i個階段和前 i1個階段之間的關(guān)系。 說明 ? 利用前兩個優(yōu)化基本可以出解 ? 第 3個優(yōu)化，對每條流水線進行動態(tài)規(guī)劃的剩余時間多少比較難確定，否則正確性難以保證，剩余時間越多，正確率越高，速度越慢。 ? 如果前 x1條流水線只要生產(chǎn) i’漢堡， j’個薯條，生產(chǎn)的飲料為 f(x1,i’,j’) ? 因此有第 x條流水線必須生產(chǎn)了 ii’個漢堡， jj’個薯條，剩下的時間生產(chǎn) k個飲料。 ?A[j]表示其中 第 j種錢幣的面值。程序如下： 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[jw[i]]+c[i],f[j]) end。 ? 由于每種物品有選和不選兩種情況，可以將每種物品的2k個當(dāng)成一個整體考慮。 ? 第 i件物品限制最多只能取 Xi個； ? 問選取裝載哪些物品，使得卡車運送的總價值最大？ 分析 ? 我們可以類似 01背包問題，將第 i種物品拆分成x[i]個，這樣每個物品只有 1件了 ,如下圖 : ? 然后對所有的物品采用動態(tài)規(guī)劃即可。 動態(tài)規(guī)劃 ? 設(shè) F(i,j)表示前 i件物品背包為 j的最大效益，則有 ? 1=i=N, 0=j=N ? 初值： F(0,j)=0， F(1,j)= ∞ ? F(N,M)即答案 ? 顯然時間復(fù)雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFMa xjiF),1(],[])[,1(),(帶條件的背包問題（ 1） ? 有 N件物品 。 //初始化 for i:=1 to n do f[i,0]:=0。 ? 第 i件物品 Wi公斤 。 滿背包問題（ 01背包） ? 有 N件物品 。 ? 第 i件物品可能帶 0~2個附件； ? 若裝載附件，必須裝載主件，反之沒有約束； ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 第 i件物品價值 Ci元 。 ? 這樣第 i種物品的個數(shù)為 k=㏒ 2 (m/wi)物品，是一個很大的改進。 分析 ? 用機器數(shù)來做狀態(tài) ， 數(shù)組 f(i,j)表示前 i個公司分配 j臺機器的最大盈利 。 顯然備用件越多 ， 系統(tǒng)可靠性越高 ， 但費用也越大 ， 那么在一定總費用限制下 ， 系統(tǒng)的最高可靠性等于多少 ？ ? 給定一些系統(tǒng)備用件的單
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1