資源背包動(dòng)態(tài)規(guī)劃ppt課件-文庫吧資料
2025-05-09 18:27本頁面
【正文】 [jw[i]]+c[i],f[j]) end。 end。 ? 進(jìn)一步 , 在計(jì)算 k時(shí) , K =㏒ 2 (j/wi), j為當(dāng)前背包剩余空間。例如第 i種物品要選 10個(gè)，則 10=23+21 。 ? 由于每種物品有選和不選兩種情況，可以將每種物品的2k個(gè)當(dāng)成一個(gè)整體考慮。 ? 若兩件物品 i、 j滿足 c[i]=c[j]且 w[i]=w[j],則將物品 i去掉 ,不用考慮。 ? 現(xiàn)有一輛載重 M公斤的卡車 。 ? 第 i件物品 Wi公斤 。 ? 第 i件物品限制最多只能取 Xi個(gè)； ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 分析 ? 我們可以類似 01背包問題，將第 i種物品拆分成x[i]個(gè)，這樣每個(gè)物品只有 1件了 ,如下圖 : ? 然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。 ? 第 i件物品價(jià)值 Ci元 。 ? 問選取裝載哪些物品，使得卡車運(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件物品價(jià)值 Ci元 。 動(dòng)態(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)即答案 ? 顯然時(shí)間復(fù)雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFMa xjiF),1(],[])
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1