資源背包動(dòng)態(tài)規(guī)劃ppt課件-在線瀏覽
2025-06-20 18:27本頁(yè)面
【正文】 c[i] } ? 0=k*w[i]=j 完全背包問(wèn)題 ? 有 N件物品 。 ? 第 i件物品價(jià)值 Ci元 。 ? 每次可以選取某種物品的任意多件裝載； ? 問(wèn)選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 類似多層背包問(wèn)題將每個(gè)物品展開(kāi)成 X[i ]=m/w[i]個(gè)，然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高的 j換成物美價(jià)廉的 i,得到至少不會(huì)更差的方案。這樣對(duì)于某種物品要選取多個(gè)，都可以由若干個(gè) 2k個(gè)物品進(jìn)行組合 (即 2進(jìn)制數(shù) )。 ? 這樣第 i種物品的個(gè)數(shù)為 k=㏒ 2 (m/wi)物品，是一個(gè)很大的改進(jìn)。 進(jìn)一步 for i:=1 to n do // 動(dòng)態(tài)規(guī)劃，遞推求 f for j:=m downto 1 do begin if j=w[i] then //背包容量夠大 f[i,j]:=max(f[i1,jw[i]]+c[i],f[i1,j]) else //背包容量不足 f[i,j]:=f[i1,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ù)更新。 思考題 1：機(jī)器分配 ? M臺(tái)設(shè)備 ， 分給 N個(gè)公司 。 分析 ? 用機(jī)器數(shù)來(lái)做狀態(tài) ， 數(shù)組 f(i,j)表示前 i個(gè)公司分配 j臺(tái)機(jī)器的最大盈利 。 ?剩下錢(qián)數(shù)最少的找零方案中的所需的最少硬幣數(shù)。顯然有： ?F[i]=Min{F[ i A[j] ] + 1} { i≤ T， 1≤j≤N} ?初始值： F[0]=0。 ?時(shí)間復(fù)雜度為 O(N*T)。 顯然備用件越多 ， 系統(tǒng)可靠性越高 ， 但費(fèi)用也越大 ， 那么在一定總費(fèi)用限制下 ， 系統(tǒng)的最高可靠性等于多少 ？ ? 給定一些系統(tǒng)備用件的單價(jià) Ck，以及當(dāng)用 Mk個(gè)此備用件時(shí)部件的正常工作概率 Pk（ Mk），總費(fèi)用上限 C。 樣例 輸入文件格式： 第一行： 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1