動(dòng)歸背包

1、背包問(wèn)題之背包問(wèn)題之PAL遞歸動(dòng)歸精講遞歸動(dòng)歸精講在M件物品取出若干件放在空間為W的背包里，每件物品的重量為W1，W2……Wn，與之相對(duì)應(yīng)的價(jià)值為P1P2……Pn。求出獲得最大價(jià)值的方案。注意：在本題中，所有的重量值均為整數(shù)。[算法分析]：對(duì)于背包問(wèn)題，通常的處理方法是搜索。用遞歸來(lái)完成搜索，算法設(shè)計(jì)如下：functionmake(i處理到第i件物品j剩余的空間為j:integer):integer初始時(shí)i=mj=背包總?cè)萘縝egini

2、fi:=0thenmake:=0ifj=wthen(背包剩余空間可以放下物品i)r1:=make(i1jw)v(第i件物品放入所能得到的價(jià)值)r2:=make(i1j)(第i件物品不放所能得到的價(jià)值)make:=max(r1r2)別告訴我學(xué)了這么多年一個(gè)max函數(shù)不會(huì)編end你別看這個(gè)遞歸小小的執(zhí)行make差不多2^n次差不多就是那一種每一個(gè)包選還是不選這個(gè)算法的時(shí)間復(fù)雜度是o(2^n)，我們可以做一些簡(jiǎn)單的優(yōu)化。由于本題中的所有物品的

3、重量均為整數(shù)，經(jīng)過(guò)幾次的選擇后背包的剩余空間可能會(huì)相等，在搜索中會(huì)重復(fù)計(jì)算這些結(jié)點(diǎn)，所以，如果我們把搜索過(guò)程中計(jì)算過(guò)的結(jié)點(diǎn)的值記錄下來(lái)，以保證不重復(fù)計(jì)算的話，[table=38.59%][tr][td]proceduremakebeginfi:=0towdof[0i]:=0fi:=1tomdofj:=0towdobeginf[ij]:=f[i1j]if(j=w)(f[i1jw]vf[ij])thenf[ij]:=f[i1jw]vendw