動態(tài)規(guī)劃背包問題ppt課件(參考版)
2025-05-09 12:09本頁面
【正文】 ? 設(shè)前 i個點的消耗 j的資源得到的最優(yōu)值，研究前 i1個點消耗的資源的最優(yōu)值，利用第 i個點決策轉(zhuǎn)移，如下圖。下圖是對第 3個優(yōu)化的說明： 30 總結(jié) ?第 1步：采用優(yōu)化方法 3，將每條流水線的 部分時間按成套生產(chǎn)，設(shè)第 i條流水線生產(chǎn)套餐 Wi套，剩下的時間為 Ti； ?第 2步，對每條流水線的剩下時間進行動態(tài)規(guī)劃 ,并采用優(yōu)化 1， 2； ?第 3步，求總套數(shù) = 貪心總套數(shù) X + 動態(tài)規(guī)劃的套數(shù) Y。 3. 讓每條流水線大多數(shù)時間按成套時間生產(chǎn)，留下一些時間進行動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，極大地減少每種物品的產(chǎn)量從而極大地減少動態(tài)規(guī)劃的狀態(tài)數(shù)。(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可以實時求出 ?時間復(fù)雜度為 10*1002*1002=109 ?顯然超時！ 28 優(yōu)化 1. 求出最多可能生產(chǎn)多少套，減少不必要循環(huán)。(ppjjpiiTxk ?????26 流水線資源分配圖 32*)39。 ? 因為前 x條流水線生產(chǎn)的飲料 = 前 x1條流水線生產(chǎn)的飲料 + 第 x條流水線生產(chǎn)的飲料 ? 所以有， f(x,i,j)=max{f(x1,i’,j’)+k} 32*)39。因此， ?假設(shè)第 i條流水線生產(chǎn)了 i’個漢堡， j’個薯條 ,那么還能生產(chǎn)飲料個數(shù)為： k’=(Tii’*p1j’*p2)/p3 25 動態(tài)規(guī)劃 ? 設(shè) f(x,i,j)表示前 x條流水線生產(chǎn) i個漢堡， j個薯條最多還能生產(chǎn)飲料個數(shù)。 21 樣例 輸入文件格式： 第一行： n C 第二行： C1 P1(0) P1(1) … P1(X1) （ 0=X1=[C/Ck]） … 第 n 行： Cn Pn(0) Pn(1) … Pn(Xn) （ 0=Xn=[C/Cn]） 輸入： 2 20 3 5 輸出： 22 分析 ?設(shè) f(i,j)表示將 j的資金用到前 i項備用件中去的最大可靠性 ， 則有 F(i,j)= max{F(i1,j–k*Cost[i])*P[i,k]} ? 0=i=n, 0=j=C,0=kj div Cost(i) ?初始： F(0,0)=0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1