1、,01背包問(wèn)題動(dòng)態(tài)規(guī)劃,首先給出數(shù)據(jù)：物品的個(gè)數(shù)是4，w , v分別為(2,3),(1,2),(3,4),(2,2);背包容量為5,表示沒(méi)有物品放入,表示背包沒(méi)有空間可以放東西,所以這些單元格里面都填入0，即價(jià)值為0,當(dāng)空間為1的時(shí)候，只能放下一件價(jià)值為2的物品,從第一個(gè)物品開(kāi)始放入，則當(dāng)空間夠第一個(gè)物品使用的時(shí)候，其他空間比第一個(gè)物品所需空間大的背包也可以放下第一個(gè)物品。,整體來(lái)說(shuō)，需要考慮的是： 1、當(dāng)前包內(nèi)所占用的空間和總的價(jià)值。 2、如果我把當(dāng)前的物品不放進(jìn)包里，那么包內(nèi)的價(jià)值會(huì)保持上一次操作的結(jié)果。 3、如果，我把當(dāng)前的物品放進(jìn)包內(nèi)會(huì)發(fā)生什么變化：我要把當(dāng)前物品放進(jìn)去，肯定要給他足夠

2、的空間，如果空間不夠，自然是放不進(jìn)去的，如果空間夠了，那么我會(huì)把之前放入的物品拿出來(lái)一些，為當(dāng)前的物品騰出空間。但是這時(shí)，我就得判斷一下，我把當(dāng)前物品放進(jìn)去后，包內(nèi)的總價(jià)值是不是比原來(lái)的高，（也可以這樣考慮，我拿出的那一部分物品的價(jià)值是不是比當(dāng)前物品的價(jià)值要高）如果不是，那么我就無(wú)需把當(dāng)前的物品放進(jìn)去了，因?yàn)榈貌坏轿蚁胍慕Y(jié)果。如果是，就放進(jìn)去。,Dpi+1j-wi+vi,#include using namespace std; #include using namespace std; int n,W; int w10,v10; int dp1010; int max(int x,int y) if(xy)return x; else return y; void slove() coutnW; for(int i=0;iwivi; slove(); return 0; ,/該方法是使用的記憶搜索的方法，請(qǐng)自行簡(jiǎn)化。 Int rec( int I , int j) int res; if(i=n) res=0; /表明物品已經(jīng)放完了。 else if(jwi) res=rec(i+1,j);/此時(shí)包內(nèi)的空間不夠放下第I個(gè)物品。 else res=max(rec(i+1,j),rec(i+1,j-wi)+vi); / 進(jìn)行比較，如果放入物品的價(jià)值