算法：0-1背包問題

看b站一個人講的，雖然講的不好，但是課件做的還是挺不錯的，拿來借鑒一下（2333）

下面開始講解：

m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優值。

m(i+1，j)可選擇物品為i+1，…，n時0-1背包問題的最優解。

m(n，j)可選擇物品為n時0-1背包問題的最優值，規模已為1

易知：

遞歸式推導：

是否将第i件物品放入？

如果不放，背包目前産生價值仍為m(i+1，j)；

如果放入，調整背包容量j-wi，背包目前産生價值為 m(i+1, j-wi ) + vi

遞歸式：

僞代碼：

void KnapSack(int v[],int w[],int c,int n,int m[][11])

{

int jMax=min(w[n]-1,c); 

for (j=0;j<jMax;j++) 

m[n][j]=0;

for (j=w[n];j<=c;j++) // 當j>=w[n]時, m(n,j)=v[n]

m[n][j]=v[n];

for (i=n-1;i>=1;i--)

{

int jMax=min(w[i]-1,c);

for (j=0;j<jMax;j++) 

m[i][j]=m[i+1][j];

for (j=w[i];j<=c;j++) //當j>=w[n]，m(n,j)=v[n]

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

}

cout<<m[1][c]; 

}      

要知道哪個物體被選中了，隻需使用倒推法：

void traceback(int m[][11],int w[],int c,int n,int x[])

{ for(i=1;i<n;i++)

if (m[i][c]==m[i+1][c])

x[i]=0;

else

{x[i]=1;c=c-w[i];}

x[n]=(m[n][c]>0 ? 1:0);

}      

源代碼：

#include<bits/stdc++.h>
using namespace std; 
int n,c;
int m[2000][2000];
void Knapsack(int *v,int *w,int c,int n)
{
  int jMax = min(w[n]-1,c);
  for(int j=0;j<=jMax;j++)/*
  當 0=<j<w[n]時, 并不能将物體放入背包，m(n,j)=0
  */
    m[n][j] = 0;
  for(int j=w[n];j<=c;j++)// 當j>=w[n]時, m(n,j)=v[n]
    m[n][j] = v[n];
  for(int i=n-1;i>1;i--)
  {
    jMax = min(w[i]-1,c);
    for(int j=0;j<=jMax;j++)//當0=<j<w[i]，m(i,j)=m(i+1,j)
      m[i][j] = m[i+1][j];
    for(int j=w[i];j<=c;j++)
      m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//當j>=w[n]，m(n,j)=v[n]
  }
  m[1][c] = m[2][c];
  if(c>=w[1])
  {
    m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
  }
  //自此，m[i][j]表填充完畢 
}


void Traceback(int *w,int c,int n,int *x)
{
  for(int i=1;i<n;i++)
    if(m[i][c] == m[i+1][c])//如果第一個m【i】【c】的價值等于m【i+1】【c】，則物品i未裝入 
      x[i] = 0;
    else//否則裝入，容量減去w【i】 
    {
      x[i] = 1;
      c-=w[i];
    }
    x[n] = (m[n][c])?1:0;//最後一個m【n】【c】大于0則代表裝入，否則，未裝入 
}
int main()
{
  cout<<"輸入物品個數n：";
  cin>>n;
  cout<<endl;
  int w[n+1];
  int v[n+1];
  cout<<"請依次輸入每個物品的重量："<<endl;
  for(int i=1;i<=n;i++)
  {
    cin>>w[i];
  }
  cout<<"請輸依次入每個物品的價值："<<endl;
  for(int i=1;i<n+1;i++)
  {
    cin>>v[i];
  }
  cout<<"輸入背包容量c：";
  cin>>c;
  Knapsack(v,w,c,n);
  int x[n+1];
  Traceback(w,c,n,x);
  cout<<endl<<"背包最大價值為"<<m[1][c]<<endl;
  for(int i=1;i<n+1;i++)
  {
    if(x[i]==1)
      cout<<"将第"<<i<<"件物品放入背包"<<endl;
  }
  cout<<"填充的m【1-4】【0-5】表"<<endl; 
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<=c;j++)
    {
      cout<<m[i][j]<<" ";
    }
    cout<<endl;
  }
  return 0;
}