動態(tài)規(guī)劃背包問題ppt課件-文庫吧資料
2025-05-12 12:09本頁面
【正文】 ?目標(biāo)： F(n,C) ?時間復(fù)雜度： O(k*n*C)， 這里 k是常數(shù)因子 ， 與數(shù)據(jù)相關(guān) 23 思考題 4：快餐問題 ?套餐由由 A個漢堡， B個薯條和 C個飲料組成 ?生產(chǎn)漢堡、薯條、飲料的時間為 p1,p2,p3 ?有 N條流水線， N=10，第 i條流水線生產(chǎn)時間為Ti ?每條流水線都可生產(chǎn)漢堡、薯條和飲料 ?每天漢堡、薯條和飲料個數(shù)不超過 100 ?如何安排生產(chǎn)使得生產(chǎn)套餐數(shù)量最多。 顯然備用件越多 ， 系統(tǒng)可靠性越高 ， 但費用也越大 ，那么在一定總費用限制下 ， 系統(tǒng)的最高可靠性等于多少 ？ ?給定一些系統(tǒng)備用件的單價 Ck，以及當(dāng)用 Mk個此備用件時部件的正常工作概率 Pk（ Mk），總費用上限 C。 ?時間復(fù)雜度為 O(N*T)。顯然有： ? F[i]=Min{F[ i A[j] ] + 1} { i≤ T， 1≤j≤N} ?初始值： F[0]=0。 ?剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。 17 分析 ?用機(jī)器數(shù)來做狀態(tài) ， 數(shù)組 f(i,j)表示前 i個公司分配j臺機(jī)器的最大盈利 。 16 思考題 1：機(jī)器分配 ?M臺設(shè)備 ， 分給 N個公司 。 在這里為了使得每個物品只取 1個或不取 ,采用了每次取 j都是與 i1進(jìn)行比較，實際上保存了每 1步取不同 j的值 15 改進(jìn)程序 ?事實上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心f(j),因此，在對 f(j)更新時，只要背包容量可以，那么可以反復(fù)更新。 14 進(jìn)一步 for i:=1 to n do // 動態(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]。 ?這樣第 i種物品的個數(shù)為 k=㏒ 2 (m/wi)物品，是一個很大的改進(jìn)。這樣對于某種物品要選取多個，都可以由若干個 2k個物品進(jìn)行組合 (即 2進(jìn)制數(shù) )。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的 j換成物美價廉的 i,得到至少不會更差的方案。 ?每次可以選取某種物品的任意多件裝載； ?問選取裝載哪些物品，使得卡車運送的總價值最大？ 13 分析 ?類似多層背包問題將每個物品展開成
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1