0-1背包問(wèn)題： 

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

 這個(gè)問(wèn)題的特點(diǎn)是：每種物品只有一件，可以選擇放或者不放。

算法基本思想：

利用動(dòng)態(tài)規(guī)劃思想 ，子問(wèn)題為：f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。

其狀態(tài)轉(zhuǎn)移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}    //這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。

解釋一下上面的方程：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，如果只考慮第i件物品放或者不放，那么就可以轉(zhuǎn)化為只涉及前i-1件物品的問(wèn)題，即1、如果不放第i件物品，則問(wèn)題轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；2、如果放第i件物品，則問(wèn)題轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”(此時(shí)能獲得的最大價(jià)值就是f [i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i])。則f[i][v]的值就是1、2中最大的那個(gè)值。

（注意：f[i][v]有意義當(dāng)且僅當(dāng)存在一個(gè)前i件物品的子集，其費(fèi)用總和為v。所以按照這個(gè)方程遞推完畢后，最終的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。）

優(yōu)化空間復(fù)雜度：

以上方法的時(shí)間和空間復(fù)雜度均為O(N*V)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以?xún)?yōu)化到O(V)。

上面f[i][v]使用二維數(shù)組存儲(chǔ)的，可以?xún)?yōu)化為一維數(shù)組f[v]，將主循環(huán)改為：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

即將第二層循環(huán)改為從V..0，逆序。

解釋一下：

假設(shè)最大容量M=10，物品個(gè)數(shù)N=3，物品大小w{3,4,5}，物品價(jià)值p{4,5,6}。

當(dāng)進(jìn)行第i次循環(huán)時(shí)，f[v]中保存的是上次循環(huán)產(chǎn)生的結(jié)果，即第i-1次循環(huán)的結(jié)果(i>=1)。所以f[v]=max{f[v],f[v-c[i]]+w[i]}這個(gè)式子中，等號(hào)右邊的f[v]和f[v-c[i]]+w[i]都是前一次循環(huán)產(chǎn)生的值。

當(dāng)i=1時(shí)，f[0..10]初始值都為0。所以

f[10]=max{f[10],f[10-c[1]]+w[1]}=max{0,f[7]+4}=max{0,0+4}=4;

f[9]=max{f[9],f[9-c[1]]+w[1]}=max{0,f[6]+4}=max{0,0+4}=4;

......

f[3]=max{f[3],f[3-c[1]]+w[1]}=max{0,f[3]+4}=max{0,0+4}=4;

f[2]=max{f[2],f[2-c[1]]+w[1]}=max{0,f[2-3]+4}=0;//數(shù)組越界？

f[1]=0;

f[0]=0;

當(dāng)i=2時(shí)，此時(shí)f[0..10]經(jīng)過(guò)上次循環(huán)后，都已經(jīng)被重新賦值，即f[0..2]=0,f[3..10]=4。利用f[v]=max{f[v],f[v-c[i]]+w[i]}這個(gè)公式計(jì)算i=2時(shí)的f[0..10]的值。

當(dāng)i=3時(shí)同理。

具體的值如下表所示：

因此，利用逆序循環(huán)就可以保證在計(jì)算f[v]時(shí)，公式f[v]=max{f[v],f[v-c[i]]+w[i]}中等號(hào)右邊的f[v]和f[v-c[i]]+w[i]保存的是f[i-1][v]和f[i -1][v-c[i]]的值。

當(dāng)i=N時(shí)，得到的f[V]即為要求的最優(yōu)值。

初始化的細(xì)節(jié)問(wèn)題：

 在求最優(yōu)解的背包問(wèn)題中，一般有兩種不同的問(wèn)法：1、要求“恰好裝滿(mǎn)背包”時(shí)的最優(yōu)解；2、求小于等于背包容量的最優(yōu)解，即不一定恰好裝滿(mǎn)背包。

這兩種問(wèn)法，在初始化的時(shí)候是不同的。

1、要求“恰好裝滿(mǎn)背包”時(shí)的最優(yōu)解：

在初始化時(shí)除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿(mǎn)背包的最優(yōu)解。如果不能恰好滿(mǎn)足背包容量，即不能得到f[V]的最優(yōu)值，則此時(shí)f[V]=-∞，這樣就能表示沒(méi)有找到恰好滿(mǎn)足背包容量的最優(yōu)值。

2、求小于等于背包容量的最優(yōu)解，即不一定恰好裝滿(mǎn)背包：

如果并沒(méi)有要求必須把背包裝滿(mǎn)，而是只希望價(jià)值盡量大，初始化時(shí)應(yīng)該將f[0..V]全部設(shè)為0。

總結(jié)

01背包問(wèn)題是最基本的背包問(wèn)題，它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類(lèi)型的背包問(wèn)題往往也可以轉(zhuǎn)換成01背包問(wèn)題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。

0-1背包問(wèn)題代碼：

代碼1

#include <iostream>
#include <vector>
using namespace std;
const int MIN=0x80000000;
const int N=3;   //物品數(shù)量
const int V=5;  //背包容量
int f[N+1][V+1];

int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[])
{
 int W[4]={0,7,5,8};      //物品權(quán)重
 int C[4]={0,2,3,4};      //物品大小
 int result=Package(W,C,N,V);
 if(result>0)
 {
  cout<<endl;
  cout<<"the opt value:"<<result<<endl;
  int i=N,j=V;
  while(i)
  {
   if(f[i][j]==(f[i-1][j-C[i]]+W[i]))
   {
    cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<endl;
    j-=C[i];
   }
   i--;
  }
 }
 else
  cout<<"can not find the opt value"<<endl;
 return;
}

int Package(int *W,int *C,int N,int V)
{
 int i,j;
 memset(f,0,sizeof(f));  //初始化為0

 for(i=0;i<=N;i++)
 for(j=1;j<=V;j++)               //此步驟是解決是否恰好滿(mǎn)足背包容量，
  f[i][j]=MIN;                //若“恰好”滿(mǎn)足背包容量，即正好裝滿(mǎn)背包，則加上此步驟，若不需要“恰好”，則初始化為0
    
 for(i=1;i<=N;i++)
  for(j=C[i];j<=V;j++)
  {
   f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);
   cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
  }
 return f[N][V];
}

代碼2

#include <iostream>
#include <vector>
using namespace std;
const int MIN=0x80000000;
const int N=3;   //物品數(shù)量
const int V=5;  //背包容量
int f[V+1];

int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[])
{
 int W[4]={0,7,5,8};      //物品權(quán)重
 int C[4]={0,2,3,4};      //物品大小
 int result=Package(W,C,N,V);
 if(result>0)
 {
  cout<<endl;
  cout<<"the opt value:"<<result<<endl;
 }
 else
  cout<<"can not find the opt value"<<endl;
 return;
}

int Package(int *W,int *C,int N,int V)
{
 int i,j;
 memset(f,0,sizeof(f));  //初始化為0

 for(i=1;i<=V;i++)               //此步驟是解決是否恰好滿(mǎn)足背包容量，
  f[i]=MIN;                //若“恰好”滿(mǎn)足背包容量，即正好裝滿(mǎn)背包，則加上此步驟，若不需要“恰好”，則初始化為0
    
 for(i=1;i<=N;i++)
  for(j=V;j>=C[i];j--)    //注意此處與解法一是順序不同的，弄清原因
  {
   f[j]=(f[j]>f[j-C[i]]+W[i])?f[j]:(f[j-C[i]]+W[i]);
   cout<<"f["<<i<<"]["<<j<<"]="<<f[j]<<endl;
  }
 return f[V];
}

參考：

http://blog.sina.com.cn/s/blog_4cd99cfa0100mer2.html

http://www.cnblogs.com/tanky_woo/archive/2010/07/31/1789621.html