01背包問(wèn)題：

一個(gè)背包總?cè)萘繛閂，現(xiàn)在有N個(gè)物品，第i個(gè) 物品體積為weight[i]，價(jià)值為value[i]，現(xiàn)在往背包里面裝東西，怎么裝能使背包的內(nèi)物品價(jià)值最大？

我們可以這樣考慮：在物品比較少，背包容量比較小時(shí)怎么解決？用一個(gè)數(shù)組f[i][j]表示，在只有i個(gè)物品，容量為j的情況下背包問(wèn)題的最優(yōu)解，那么當(dāng)物品種類變大為i+1時(shí)，最優(yōu)解是什么？第i+1個(gè)物品可以選擇放進(jìn)背包或者不放進(jìn)背包（這也就是0和1），假設(shè)放進(jìn)背包（前提是放得下），那么f[i+1][j]=f[i][j-weight[i+1]+value[i+1]；如果不放進(jìn)背包，那么f[i+1][j]=f[i][j]。

由此得出狀態(tài)轉(zhuǎn)移方程：

f[i+1][j]=max(f[i][j],f[i][j-weight[i+1]+value[i+1])

給出一段代碼：  

int f[2000];//全局變量，自動(dòng)初始化為0  

int weight[10];  

int value[10];  

#define  max(x,y)   (x)>(y)?(x):(y)  

int main()  

{  

    int N,M;  

    cin>>N;//物品個(gè)數(shù) 

    cin>>M;//背包容量 

    for (int i=1;i<=N; i++)  

    {  

        cin>>weight[i]>>value[i];  

    }  

    for (int i=1; i<=N; i++)  

        for (int j=M; j>=1; j--)  

        {  

            if (weight[i]<=j)  

            {  

               f[j]=max(f[j],f[j-weight[i]]+value[i]);  

            }             

        }  

     cout<<f[M]<<endl;//輸出最優(yōu)解   

}