問答題

【簡答題】

有這樣一類特殊0-1背包問題:可選物品重量越輕的物品價(jià)值越高。
n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。
其中n為物品個(gè)數(shù),c為背包載重量,P表示物品的價(jià)值,W表示物品的重量。請問對于此0-1背包問題,應(yīng)如何選擇放進(jìn)去的物品,才能使到放進(jìn)背包的物品總價(jià)值最大,能獲得的最大總價(jià)值多少?

答案: 因?yàn)樵?-1背包問題比較特殊,恰好重量越輕的物品價(jià)值越高,所以優(yōu)先取重量輕的物品放進(jìn)背包。最終可以把重量分別為2,3,4...
微信掃碼免費(fèi)搜題