動態(tài)規(guī)劃背包問題ppt課件-展示頁
2025-05-15 12:09本頁面
【正文】 X[i ]=m/w[i]個，然后對所有的物品采用動態(tài)規(guī)劃即可。 ?第 i件物品價值 Ci元 。 ? F(i,j)=max{ f(i1,jk*w[i]) + k*c[i] } ? 0=k*w[i]=j 12 完全背包問題 ?有 N件物品 。 ?現(xiàn)有一輛載重 M公斤的卡車 。 ?第 i件物品 Wi公斤 。 ?第 i件物品可能帶 0~2個附件； ?若裝載附件，必須裝載主件，反之沒有約束； ?現(xiàn)有一輛載重 M公斤的卡車 。 ?第 i件物品 Wi公斤 。 ?問選取裝載哪些物品，使得卡車開車正好裝滿時，運送的總價值最大？ 若無法裝滿卡車，則輸出無解。 ?第 i件物品價值 Ci元 。 5 滿背包問題（ 01背包） ?有 N件物品 。 for i:=1 to n do // 動態(tài)規(guī)劃，遞推求 f for j:=1 to m 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]。 ?問選取裝載哪些物品，使得卡車運送的總價值最大？ 3 動態(tài)規(guī)劃 ?可以按每個物品進行規(guī)劃，同樣每種物品有選和不選兩種選擇 ?設(shè) F(i,j)表示前 i件物品載重為 j的最大效益，則有 ? 1=i=N, 0=j=N ?初值： F(0,j)=0 ? F(N,M)即答案 ?顯然時間復(fù)雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFM a xjiF),1(],[])[,1(),(4 主程序如下 for i:=1 to m do f[0,i]:=0。 ?第 i件物品價值 Ci元 。1 背包類動態(tài)規(guī)劃問題 2 經(jīng)典的背包問題（ 01背包） ?有 N件物品 。 ?第 i件物品 Wi公斤 。 ?現(xiàn)有一輛載重 M公斤的卡車 。 //初始化 for i:=1 to n do f[i,0]:=0。 end。 ?第 i件物品 Wi公斤 。 ?現(xiàn)有一輛載重 M公斤的卡車 。 6 動態(tài)規(guī)劃 ?設(shè) F(i,j)表示前 i件物品背包為 j的最大效益，則有 ?1=i=N, 0=j=N ?初值： F(0,j)=0， F(1,j)= ∞ ?F(N,M)即答案
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1