背包九讲（动态规划）

01背包问题

原题链接 AcWing

题目描述

n件物品，一个容量为v的背包，第i件物品的体积为vi，价值为wi，每个物品只能选择一次，求最大价值

解题思路：

首先是我在biliili上看的一个视频讲解，我感觉挺好理解的。下面是我根据这个题写的思路。

可以分为拿和不拿的情况，记f(k,w)表示当前背包容量为w，现有k件物品可拿。如果当前背包容量不够(j<v[i])，没得选，此时
$$f[i][j]=f[i-1][j];$$
若当前背包容量足够，可以选择，那么需要考虑要不要拿，此时
$$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);$$

上代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int f[1100][1100];
int v[1100],w[1100];signed main()
{IOSint n,m;memset(f,0,sizeof(f));cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(v[i]>j)f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}cout<<f[n][m]<<'\n';
}

思路2：

上面那个思路是很久前学的，这次系统的学主要是学的闫氏dp分析法。也特别好理解。

闫氏dp分析法：

二维：f[i] [j]表示前i个物品，背包容量为j下的最优解。

起始令f[0] [0]=0，不断更新f[i] [j]。

若当前背包容量不够，那么此时的最优解就是前i-1个物品的最优解，此时：f[i] [j]=f[i-1] [j];

若此时背包容量足够，那么就可以考虑究竟是选还是不选，此时：f[i] [j]=max(f[i] [j],f[i] [j-v[i]]+w[i]);

二维代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int f[1100][1100];
int v[1100],w[1100];signed main()
{IOSint n,m;memset(f,0,sizeof(f));cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}cout<<f[n][m]<<'\n';
}

优化代码：

dp问题优化代码其实就是做一个等价变形。

f[j]表示n件物品，背包容量为j下的最优解。优化代码就是直接把二维转化为一维，把前面的那个[i]直接去掉，但是注意一维枚举背包容量j必须从m开始。

原因：f[i] [j]是从上一轮i-1的状态得来的，f[i] [j]和f[i-1] [j]并不相等，优化到一维后，如果我们还是正序，那么本应该是第i-1的状态用来更新的却是第i轮的状态。简单说，就是如果正序，f[j]需要用到的前面i-1的状态已被i更新，因此我们需要逆序。

核心代码：

for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int f[1100];
int v[1100],w[1100];signed main()
{IOSint n,m;memset(f,0,sizeof(f));cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--){
// 			if(v[i]>j)
// 			f[i][j]=f[i-1][j];
// 			elsef[j]=max(f[j],f[j-v[i]]+w[i]);}cout<<f[m]<<'\n';
}

完全背包问题

原题链接 AcWing

题目描述：

和01背包不同的是每个物品可以选择无限次。

解题思路：

同样是用闫氏dp分析法，相比于01背包多可一冲循环，判断一个物品最多可以选择多少次，就是在01背包的基础加重循环枚举选择次数(k*v[i]<=j)

二维代码：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = 0 ; j<=m ;j++){for(int k = 0 ; k*v[i]<=j ; k++)f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}cout<<f[n][m]<<endl;
}

优化代码：

二维代码会TLE，所以我们就必须优化代码了。

列举一下更新次序的内部关系：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： f[i][j]=max(f[i,j-v]+w , f[i-1][j]) 

根据上面的关系，可以把k循环去掉，代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int f[1100][1100];
int v[1100],w[1100];signed main()
{IOScin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];for(int i=1;i<=n;i++)for(int j=1;j<=m;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<<f[n][m]<<endl;
}

去掉一重循环后，这题就可以过了，但是我们可以发现优化完成后，代码跟01背包非常像，对比一下：

f[i] [j] = max(f[i] [j],f[i-1] [j-v[i]]+w[i]); // 01背包

f[i] [j] = max(f[i] [j],f[i] [j-v[i]]+w[i]); // 完全背包

所以我们可以进一步优化成一维的：

for(int i=1;i<=n;i++)for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}

注意，这里的j是从小到大枚举，因为这里需要的是第i的状态。

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int f[1100];
int v[1100],w[1100];signed main()
{IOScin>>n>>m;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<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}cout<<f[m]<<endl;
}

多重背包问题

题目描述：

多重背包问题分为了 I，II，III，和01背包的不同是每个可以选择有限次

原题链接 AcWing

解题思路：

可以参考完全背包问题，就是在完全背包问题的次数循环中多了一个限制条件，k<=s[i]，所以k(次数循环)的限定条件为k<=s[i]&&k*v[i]<=j;

二维代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int f[110][110];
int v[110],w[110],s[110];signed main()
{IOScin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=s[i]&&k*v[i]<=j;k++){f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+k*w[i]);}cout<<f[n][m]<<endl;
}

优化代码1：

优化代码1就是第二个问题了。

原题链接 AcWing

首先按照完全背包优化的思路看看可不可以，对比一下：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , ..... , f[i-1,j-sv]+sw)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , ..... ,f[i-1,j-sv]+(s-1)w , f[i-1,j-(s+1)v]+sw)

显然不能用f[i,j-v]表示f[i,j]，所以不可以用完全背包的优化方式优化多重背包问题。

所以我们需要二进制优化，利用二进制将多重背包问题转化为01背包问题。

将s个物品打包成log s个新的物品组，用它们可以凑出0~s的任何一个数。时间复杂度：O(s)优化为O(log(s))

打包方法：1+2+4+……+2^k-1+2k+C=s，C<2^{(k+1)，前面可以凑出0~2}(k+1)-1，加上c就可以凑出c_{s，又由于c<2^(k+1)，所以可以凑出0}s中任意一个数。

二进制优化将n种物品，每种si个的多重背包，拆分成k件物品组的01背包问题。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5;
int f[N];
int n,m;
int v[N],w[N];signed main()
{IOScin>>n>>m;int cnt=1;for(int i=1;i<=n;i++){int a,b,s;cin>>a>>b>>s;int k=1;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s>0){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}	n=cnt;for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m]<<endl;
}

优化代码2：

优化代码2就是第3个问题了

原题链接 AcWing

题目已经给出提示，需要用单调队列优化。

首先先写出来dp方程：不放物品 i = f[i-1] [j]

​ 放k个物品 i = f[i-1] [j - kv] + kw

​ f[i] [j] = max(f[i-1] [j], f[i-1] [j-v] + w, f[i-1] [j-2v] + 2w,…, f[i-1] [j-kv] + kw)

然后用dp数组来保存上一轮的信息，令f[j]表示容量为j的情况下，获得的最大值

所以：f[m] = max(f[m], f[m-v] + w, f[m-2v] + 2w, f[m-3v] + 3w, …)

接下来，我们把 dp[0] --> dp[m] 写成下面这种形式
f[0], f[v],   f[2*v],   f[3*v],   ... , f[k*v]
f[1], f[v+1], f[2*v+1], f[3*v+1], ... , f[k*v+1]
f[2], f[v+2], f[2*v+2], f[3*v+2], ... , f[k*v+2]
...
f[j], f[v+j], f[2*v+j], f[3*v+j], ... , f[k*v+j]

显而易见，m 一定等于 k*v + j，其中 0 <= j < v。所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的。

因为我们需要的是{ dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[k*v+j] } 中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题

所以，我们可以得到
f[j]    =     f[j]
f[j+v]  = max(f[j] +  w,  f[j+v])
f[j+2v] = max(f[j] + 2w,  f[j+v] +  w, f[j+2v])
f[j+3v] = max(f[j] + 3w,  f[j+v] + 2w, f[j+2v] + w, f[j+3v])
...
由于这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换f[j]    =     f[j]
f[j+v]  = max(f[j], f[j+v] - w) + w
f[j+2v] = max(f[j], f[j+v] - w, f[j+2v] - 2w) + 2w
f[j+3v] = max(f[j], f[j+v] - w, f[j+2v] - 2w, f[j+3v] - 3w) + 3w
...
这样，每次入队的值是 f[j+k*v] - k*w

其实就是单调队列中的滑动窗口思想，保持队列元素的个数，如果不能继续入队，弹出队头元素
尾值 >= f[j + kv] - kw。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=20010;
int n,m;
int f[N],g[N],q[N];signed main()
{IOScin>>n>>m;for(int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;memcpy(g,f,sizeof f);for(int j=0;j<v;j++){int hh=0,tt=-1;for(int k=j;k<=m;k+=v){f[k]=g[k];if(hh<=tt&&k-s*v>q[hh])hh++;if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)tt--;q[++tt]=k;}}}cout<<f[m]<<endl;
}

混合背包问题

原题链接 AcWing

题目描述：

就是把01背包，完全背包，多重背包结合到一起了。

解题思路：

把这个问题转化为多重背包问题，看数据范围，多重背包问题2的代码就可以过。如果是01背包，数量就写成1，如果是完全背包，数量就写成m/a。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5;
int n,m;
int v[N],w[N];
int f[N];signed main()
{IOScin>>n>>m;int cnt=1;for(int i=1;i<=n;i++){int a,b,s;cin>>a>>b>>s;int k=1;if(s==-1) s=1;else if(s==0) s=m/a;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s>0){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}n=cnt;for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m]<<endl;
}

二维费用的背包问题：

原题链接 AcWing

题目描述：

这个题就是在原来容量的基础上加了个重量，重量也必须达标。

解题思路：

01背包的动态转移方程是：f[i] [j]=max(f[i-1] [j],f[i-1] [j-v[i]]+w[i]);

这个题就是在01 背包的基础上再加一维变成三维：f[i] [j] [k]=max(f[i-1] [j] [k],f[i-1] [j-v[i]] [k-m[i]]+w[i]);

按照01背包优化：f[j] [k]=max(f[j] [k],f[j-v[i]] [k-m[i]]);

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,v,m;
int a[1100],b[1100],w[1100];
int f[1100][1100];signed main()
{IOScin>>n>>v>>m;for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>w[i];for(int i=1;i<=n;i++)for(int j=v;j>=a[i];j--)for(int k=m;k>=b[i];k--){f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+w[i]);}cout<<f[v][m]<<endl;
}

分组背包问题：

原题链接 AcWing

题目描述：

与01背包的区别就是分组了，但是一组里面最多只能选一个。

解题思路：

和01背包差不多，对于每组s个物品，有s+1,重选法，所以，我们先循环所有体积，再循环枚举所有选择，其中k是枚举所有选择中的循环变量。f[i] [j]=max(f[i][j],f[i-1] [j-v[i] [k]]+w[i] [k]);

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int v[110][110],w[110][110],s[110];
int f[110][110];signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=0;j<s[i];j++)cin>>v[i][j]>>w[i][j];}for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];for(int k=0;k<s[i];k++){if(v[i][k]<=j)f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}cout<<f[n][m]<<endl;
}

优化代码：

仿照01背包问题优化代码，逆向枚举体积。

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int v[110][110],w[110][110],s[110];
int f[110];signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=0;j<s[i];j++)cin>>v[i][j]>>w[i][j];}for(int i=1;i<=n;i++)for(int j=m;j>0;j--)for(int k=0;k<s[i];k++){if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}cout<<f[m]<<endl;
}

背包问题求方案数：

原题链接 AcWing

题目描述：

题目与01背包相同，输出是有几个可达到最大价值的方案数。

解题思路：

定义两个数组，f[i]储存最佳方案的总价值，g[i]储存背包容积为i时总价值的方案数。先把g[i]初始化为1，循环n次，每次读入v,w，求出装新物品时的总价值，如果装新物品的方案总价值更大，f[j]=f[j-v]+w; g[j]=g[j-v]；如果总价值相等，最大价值方案就多了g[j-v]种。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m,v,w;
int g[1100],f[1100];
const int mod=1e9+7;signed main()
{IOScin>>n>>m;for(int i=0;i<=m;i++) g[i]=1;for(int i=1;i<=n;i++){cin>>v>>w;for(int j=m;j>=v;j--){int x=f[j-v]+w;if(f[j]<x){f[j]=x;g[j]=g[j-v];}else if(f[j]==x)g[j]=(g[j]+g[j-v])%mod;//cout<<j<<" "<<f[j]<<" "<<g[j]<<endl;}}cout<<g[m]<<endl;
}

背包问题求具体方案：

原题链接 AcWing

题目描述：

题目与01背包相同，求最大价值的具体方案，输出字典序最小的。

解题思路：

因为要求字典序最小的，所以我们需要倒序遍历，即当前物品既可以选又可以不选时，优先选。

先做一遍正常的01背包，然后从目标状态倒推回初始状态的整个转移路径。如果出现分叉转移，优先选当前物品。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int n,m;
int v[1100],w[1100],f[1100][1100];signed main()
{IOScin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];for(int i=n;i>0;i--)for(int j=0;j<=m;j++){f[i][j]=f[i+1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;}int i=1,j=m;while(i<=n){if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j]){cout<<i<<" ";j=j-v[i];i++;}elsei++;}
}