本文共 3951 字，大约阅读时间需要 13 分钟。

1. 01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入格式

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

数据范围

（1）状态f[i][j]定义：前 i个物品，背包容量 j下的最优解（最大价值）：

​ 当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N件物品，则需要 N 次决 策，每一次对第 i件物品的决策，状态f[i][j]不断由之前的状态更新而来。

（2）当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1 个物品最优解：

​ 对应代码：f[i][j] = f[i - 1][j]。

（3）当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：

​ 选：f[i][j] = f[i - 1][j - v[i]] + w[i]。

​ 不选：f[i][j] = f[i - 1][j]

二维形式：

每次取最大值

#include
   
    using namespace std;int V,N;int v[1005],w[1005];int f[1005][1005];int main(){    	cin>>N>>V;	for(int i=1;i<=N;i++) cin>>v[i]>>w[i];	for(int i=1;i<=N;i++)	{   		for(int j=0;j<=V;j++)		{   			f[i][j]=f[i-1][j];//			if(j>=v[i]) 				f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);		}	}	cout<
    
     <<"\n";	return 0; }
    
   

一维形式：

#include
   
    using namespace std;const int maxn = 1e3+5;int f[maxn];int v[maxn],w[maxn];int N,V;int main(){       cin>>N>>V;        for(int i=1;i<=N;i++) cin>>v[i]>>w[i];        //想象方格     for(int i=1;i<=N;i++)        for(int j=V;j>=v[i];j--)            f[j] = max(f[j],f[j-v[i]]+w[i]);                cout<
    
     <<"\n";    return 0;}
    
   

注意：体积要从v到v[i],只能降序。

2. 完全背包

二维形式：

#include
   
    using namespace std;int V,N;int v[1005],w[1005];int f[1005][1005];int main(){   	//二维 	cin>>N>>V;	for(int i=1;i<=N;i++) cin>>v[i]>>w[i];	for(int i=1;i<=N;i++)	{   		for(int j=0;j<=V;j++)		{   			f[i][j]=f[i-1][j];			if(j>=v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);		}	}	cout<
    
     <<"\n";	return 0; }
    
   

一维形式：

#include
   
    using namespace std;int N,V;int f[maxn];int main(){   	cin>>N>>V;	for(int i=1;i<=N;i++) cin>>v[i]>>w[i];	for(int i=1;i<=N;i++)	{   		for(int j=v[i];j<=V;j++)		{   			f[j] = max(f[j],f[j-v[i]]+w[i]);		}	}	cout<
    
     <<"\n";	return 0; }
    
   

注意：体积从v[i]到v。

3. 多重背包

一二维形式：

#include
   
    using namespace std;typedef long long ll;const int maxn = 1e3;const int INF = 0x3f3f3f3f;int f[maxn];int v[maxn],w[maxn],num[maxn];int N,V;int main(){   	//多重循环 	cin>>N>>V;	for(int i=1;i<=N;i++) cin>>v[i]>>w[i]>>num[i];	for(int i=1;i<=N;i++)	{   		for(int j=V;j>=0;j--)		{   			for(int k=1;k<=num[i];k++)			{   				if(j-k*v[i]>=0)					f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);//			f[i][j] = max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);			}		}	}	cout<
    
     <<"\n";	return 0;}
    
   

二进制压缩：

//二进制压缩 #include
   
    using namespace std;typedef long long ll;const int maxn = 1e3+5;int f[15005],s[maxn],w[maxn],v[maxn];int nw[15005],nv[15005];int V,N;int main(){       cin>>N>>V;    for(int i=1;i<=N;i++) cin>>v[i]>>w[i]>>s[i];    int total = 1;    for(int i=1;i<=N;i++)    {           for(int j=1;j<=s[i];j<<=1)        {               nv[total] = j*v[i];            nw[total++] = j*w[i];            s[i]-=j;        }        if(s[i])        {               nv[total] = s[i]*v[i];            nw[total++] = s[i]*w[i];        }    }    //01背包    for(int i=1;i
    
     =nv[i];j--)        {               f[j] = max(f[j],f[j-nv[i]]+nw[i]);        }    }    cout<
     
      <<"\n";    return 0;}
     
    
   

单调队列优化：

//单调队列优化#include
   
    using namespace std;int n,m;int f[20002],q[20002],g[20002];int main(){       cin>>n>>m;    for(int i=1;i<=n;i++)    {           int v,w,s;        cin>>v>>w>>s;        memcpy(g,f,sizeof(f));        //滚动数组优化空间，g[]即f[i-1][];        for(int j=0;j
    
     q[hh])                  //如果当前窗口的内容超过了s个;                {                       hh++;                }                if(hh<=tt)                 {                       f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);                     //max(f[i-1][k],f[i-1][能转移里最大]+数*v[i]);                }                while(hh<=tt && g[q[tt]]-(q[tt]-j)/v*w <= g[k]-(k-j)/v*w)                {                       tt--;                }                q[++tt]=k;            }        }    }    cout<
     
      <