01背包（ZeroOnePack）:有N件物品和一個(gè)容量為V的背包。（每種物品均只有一件）第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

完全背包(CompletePack):有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

4件物品，重量和價(jià)值如下，背包的重量為10,

01背包代碼：

//W[i]表示重量，v[i]表示價(jià)值,背包容量為gint f[x+1];//f[x]背包容量為x的最大價(jià)值for(int i=0;i<n;i++)     for(int j=g;j>=w[i];j--)          f[j]=max(f[j],f[j-w[i]]+v[i]);完全背包代碼：
for(int i=0;i<n;i++)    for(int j=w[i];j<=g;j++)         f[j]=max(f[j],f[j-w[i]]+v[i]);01背包采用j=g;j>=w[i];j--這樣可以避免一個(gè)物品被多次使用到。例如：若使用w[i]→g，被使用到的f[j-w[i]]的值可能包含這個(gè)物品w[i]，從g→w[i]保證了引用的f[j-w[i]]為沒有用到物品w[i]。
完全背包恰好可以使用這個(gè)順序，因?yàn)槲锲房梢噪S意使用只要使f最大即可
初始化分兩種情況：        1、如果背包要求正好裝滿： f[0] = 0, f[1~w] = -INF(若求最小價(jià)值，則f[1~w] = INF)
(因?yàn)榇藭r(shí)未被裝滿的話是-inf上+正數(shù)沒影響，f[0]=0，當(dāng)j=w[i]時(shí)，f[j]=f[0]+v[i]，這相當(dāng)于每件物品分別裝滿)
        2、如果不需要正好裝滿： f[0~w] = 0;  
最終結(jié)果：f[w] 即為所求  
多重背包(MultiplePack):有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
 
多重背包轉(zhuǎn)換成01背包問(wèn)題就是多了個(gè)初始化，把它的件數(shù)C用二進(jìn)制分解成若干個(gè)件數(shù)的集合，這里面數(shù)字可以組合成任意小于等于C的件數(shù)，而且不會(huì)重復(fù)，之所以叫二進(jìn)制分解，是因?yàn)檫@樣分解可以用數(shù)字的二進(jìn)制形式來(lái)解釋        比如：7的二進(jìn)制7 = 111它可以分解成001 010 100這三個(gè)數(shù)可以組合成任意小于等于7的數(shù)，而且每種組合都會(huì)得到不同的數(shù)，15 = 1111可分解成0001  0010  0100  1000四個(gè)數(shù)字        如果13 = 1101則分解為 0001 0010 0100 0110前三個(gè)數(shù)字可以組合成 7以內(nèi)任意一個(gè)數(shù)，即1、2、4可以組合為1——7內(nèi)所有的數(shù)，加上0110 = 6 可以組合成任意一個(gè)大于6小于等于13的數(shù)，比如12，可以讓前面貢獻(xiàn)6且后面也貢獻(xiàn)6就行了。雖然有重復(fù)但總是能把13以內(nèi)所有的數(shù)都考慮到了，基于這種思想去把多件物品轉(zhuǎn)換為，多種一件物品，就可用01背包求解了。
        int n,g;        cin>>g>>n;        int count=0;        for(i=0;i<=n-1;i++)        {            cin>>w[i]>>v[i]>>c[i];//對(duì)該種類的c[i]件物品進(jìn)行二進(jìn)制分解，對(duì)于13              for(j=1;j<=c[i];j=j*2)//0001,0010,0100,...依次分解            {                w0[count]=w[i]*j;                v0[count]=v[i]*j;                count++;                c[i]=c[i]-j;            }            if(c[i]>0)//對(duì)剩余的1000進(jìn)行儲(chǔ)存            {                w0[count]=w[i]*c[i];                v0[count]=v[i]*c[i];                count++;            }        }1.//經(jīng)過(guò)上面對(duì)每一種物品的分解，  2.        //現(xiàn)在v0[]存的就是分解后的物品價(jià)值  3.        //w0[]存的就是分解后的物品重量  4.        //count就相當(dāng)于原來(lái)的n  5.        //下面就直接用01背包算法來(lái)解          memset(f,0,sizeof(f));        for(i=0;i<=count-1;i++)            for(j=g;j>=w0[i];j--)            f[j]=max(f[j],f[j-w0[i]]+v0[i]);