資源背包動(dòng)態(tài)規(guī)劃ppt課件(更新版)
【正文】 一輛載重 M公斤的卡車 。 ? 第 i件物品價(jià)值 Ci元 。 ? 第 i件物品 Wi公斤 。 ? 每次可以選取某種物品的任意多件裝載； ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 類似多層背包問題將每個(gè)物品展開成 X[i ]=m/w[i]個(gè)，然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。 進(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]。 ?剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。 樣例 輸入文件格式： 第一行： 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 輸出： 分析 ? 設(shè) f(i,j)表示將 j的資金用到前 i項(xiàng)備用件中去的最大可靠性 ， 則有 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 ? 目標(biāo)： F(n,C) ? 時(shí)間復(fù)雜度： O(k*n*C)， 這里 k是常數(shù)因子， 與數(shù)據(jù)相關(guān) 思考題 4：快餐問題 ? 套餐由由 A個(gè)漢堡， B個(gè)薯?xiàng)l和 C個(gè)飲料組成 ? 生產(chǎn)漢堡、薯?xiàng)l、飲料的時(shí)間為 p1,p2,p3 ? 有 N條流水線， N=10，第 i條流水線生產(chǎn)時(shí)間為 Ti ? 每條流水線都可生產(chǎn)漢堡、薯?xiàng)l和飲料 ? 每天漢堡、薯?xiàng)l和飲料個(gè)數(shù)不超過 100 ? 如何安排生產(chǎn)使得生產(chǎn)套餐數(shù)量最多。(ppjjpiiTxk ?????其中，思考？ ? f(x,i,j)=max{f(x1,i’,j’)+k} 1=x=n=10,0=i’=i=100, 0=j’=j=100 ? k可以實(shí)時(shí)求出 ? 時(shí)間復(fù)雜度為 10*1002*1002=109 ? 顯然超時(shí)！ 優(yōu)化 1. 求出最多可能生產(chǎn)多少套，減少不必要循環(huán)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1