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