資源背包動態(tài)規(guī)劃ppt課件-wenkub
2023-05-18 18:27:15 本頁面
【正文】 ? 1=i=N, 0=j=N ? 初值： F(0,j)=0 ? F(N,M)即答案 ? 顯然時間復雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFMa xjiF),1(],[])[,1(),(主程序如下 for i:=1 to m do f[0,i]:=0。 ? 第 i件物品 Wi公斤 。 ? 第 i件物品價值 Ci元 。 //初始化 for i:=1 to n do f[i,0]:=0。 ? 第 i件物品 Wi公斤 。 動態(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)即答案 ? 顯然時間復雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFMa xjiF),1(],[])[,1(),(帶條件的背包問題（ 1） ? 有 N件物品 。 ? 問選取裝載哪些物品，使得卡車運送的總價值最大？ 分析 ? 假設(shè)只有主件的情況 ，顯然與經(jīng)典背包問題完全相同！ ? 現(xiàn)在每個物品有附件，我們可以分成 4種方案 – 僅裝載主件 – 裝載主件 +第 1個附件 – 裝載主件 +第 2個附件 – 裝載主件 +2個附件 ? 由于上述 4種并列，這是幾種不同的決策同時規(guī)劃即可 動態(tài)規(guī)劃 ? 設(shè) F(i,j)表示前 i件物品背包為 j的最優(yōu)解，則有， ? 1=i=N, 0=j=M ? 時間復雜度 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件物品 。 ? 第 i件物品限制最多只能取 Xi個； ? 問選取裝載哪些物品，使得卡車運送的總價值最大？ 分析 ? 我們可以類似 01背包問題，將第 i種物品拆分成x[i]個，這樣每個物品只有 1件
教學課件相關(guān)推薦
鄂ICP備17016276號-1