資源背包動(dòng)態(tài)規(guī)劃ppt課件(完整版)
【正文】 全相同！ ? 現(xiàn)在每個(gè)物品有附件，我們可以分成 4種方案 – 僅裝載主件 – 裝載主件 +第 1個(gè)附件 – 裝載主件 +第 2個(gè)附件 – 裝載主件 +2個(gè)附件 ? 由于上述 4種并列，這是幾種不同的決策同時(shí)規(guī)劃即可 動(dòng)態(tài)規(guī)劃 ? 設(shè) F(i,j)表示前 i件物品背包為 j的最優(yōu)解，則有， ? 1=i=N, 0=j=M ? 時(shí)間復(fù)雜度 O(NM) ???????????????????????????????件附件選主件和，件附件選主件和第，件附件選主件和第，只選主件件物品不選第2//]2[]1[][])2[]1[w][,1(2//]2[][])2[][,1(1//]1[][])1[w][,1(][])[,1(i),1(),(iciciciwiiwjiFiciciwiwjiFiciciiwjiFiciwjiFjiFM a xjiF多層背包問題 ? 有 N件物品 。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 進(jìn)一步 , 在計(jì)算 k時(shí) , K =㏒ 2 (j/wi), j為當(dāng)前背包剩余空間。 則狀態(tài)轉(zhuǎn)移方程為 : ? f(i,j) =Max{f[i1， k] + a[i， jj]} (1=i=N,1=j=M,0=k=j ) ? 初始值 : f(0,0)=0 ? 時(shí)間復(fù)雜度 O(N*M2) 思考題 2：硬幣找零 ?給定 N枚硬幣 ?給定 T元錢 ?用這 N枚硬幣找這 T元錢，使得剩下的錢最少。求系統(tǒng)可能的最高可靠性。(1*)39。 ? 狀態(tài)轉(zhuǎn)移方程一般可寫成 : fi(j) = min{ fi1 ( k) + ui (j,k)} 。 2. 淘汰一些沒有意義狀態(tài)，比如生產(chǎn)了過多第三種物質(zhì)，卻沒把前兩種生產(chǎn)滿。 分析 ? 對(duì)于每條流水線，它的生產(chǎn)時(shí)間是一定的，我們?nèi)绻懒松a(chǎn)漢堡和薯?xiàng)l的個(gè)數(shù)，就很容易計(jì)算出生產(chǎn)飲料的個(gè)數(shù)。 ?N=500,T=10000. 分析 ?設(shè) F[i]表示需要找的錢數(shù)為 i時(shí)所需要的最少錢幣數(shù)。 end。 ? 若兩件物品 i、 j滿足 c[i]=c[j]且 w[i]=w[j],則將物品 i去掉 ,不用考慮。 ? 第 i件物品價(jià)值 Ci元 。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 搜索法 ? 對(duì)于每種物品，要么裝上卡車，要么不裝，因此， N種物品的裝箱方案共有 2N種。 ? 現(xiàn)有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1