《資源背包動(dòng)態(tài)規(guī)劃》ppt課件-文庫吧
2025-04-18 18:27 本頁面
【正文】 ),1(],[])[,1(),(帶條件的背包問題（ 1） ? 有 N件物品 。 ? 第 i件物品 Wi公斤 。 ? 第 i件物品價(jià)值 Ci元 。 ? 第 i件物品可能帶 0~2個(gè)附件； ? 若裝載附件，必須裝載主件，反之沒有約束； ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 假設(shè)只有主件的情況 ，顯然與經(jīng)典背包問題完全相同！ ? 現(xiàn)在每個(gè)物品有附件，我們可以分成 4種方案 – 僅裝載主件 – 裝載主件 +第 1個(gè)附件 – 裝載主件 +第 2個(gè)附件 – 裝載主件 +2個(gè)附件 ? 由于上述 4種并列，這是幾種不同的決策同時(shí)規(guī)劃即可 動(dòng)態(tài)規(guī)劃 ? 設(shè) F(i,j)表示前 i件物品背包為 j的最優(yōu)解，則有， ? 1=i=N, 0=j=M ? 時(shí)間復(fù)雜度 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件物品 Wi公斤 。 ? 第 i件物品價(jià)值 Ci元 。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 第 i件物品限制最多只能取 Xi個(gè)； ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 我們可以類似 01背包問題，將第 i種物品拆分成x[i]個(gè)，這樣每個(gè)物品只有 1件了 ,如下圖 : ? 然后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。 ? F(i,j)=max{ f(i1,jk*w[i]) + k*c[i] } ? 0=k*w[i]=j 完全背包問題 ? 有 N件物品 。 ? 第 i件物品 Wi公斤 。 ? 第 i件物品價(jià)值 Ci元 。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 每次可以選取某種物品的任意多件裝載； ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 類似多層背包問題將每個(gè)物品展開成 X[i ]=m/w[i]個(gè)，然后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。 ? 若兩件物品 i、 j滿足 c[i]=c[j
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1