背包问题总结
一、01背包
原题链接：2. 01背包问题 - AcWing题库
思路分析
dp问题最重要的是状态转移方程。那么我们首先来定义一下状态：
dp[i][j] 表示前 i 个物品，背包容量不超过 j 时的最大价值。
那么要怎么更新状态呢？
- 当背包容量不够时（
j < v[i]) 没得选，所以前 i 个物品的最大值就是前 i-1 个物品的最大值 - 当容量够时 (
j >= v[i]) ，可以选，所以我们需要决定是否需要选。- 选：
dp[i][j] = dp[i-1][j-v[i]]+w[i] - 不选：
dp[i][j] = dp[i-1][j] - 所以我们要取max
- 选：
代码如下
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值
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 = 1; j <= m; j++)
{
// 当前背包容量装不进第i个物品，则价值等于前i-1个物品
if(j < v[i])
f[i][j] = f[i - 1][j];
// 能装，需进行决策是否选择第i个物品
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
优化版本
第二维枚举时 需要逆序
- 在二维情况下，状态
f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。 - 状态转移方程为
f[j] = max(f[j], f[j - v[i]] + w[i])
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int n,m;
int dp[N];
int v[N],w[N];
int main()
{
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--)
{
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m];
return 0;
}
二、完全背包问题
原题链接：3. 完全背包问题 - AcWing题库
原始版本
#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;
}
递推优化
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])
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); //注意只有这一句与 01 背包不同！！！ 参考01背包，完全背包应该还能继续优化！
}
最终版本
#include<iostream>
using namespace std;
const int N = 1010;
int f[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 = v[i] ; j<=m ;j++)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
}
三、多重背包
原题链接：4. 多重背包问题 I - AcWing题库
首先我们知道，对于完全背包问题有：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2v]+2w,dp[i-1][j-3v]+3w,...);
dp[i][j-v]=max( dp[i-1][j-v], dp[i-1][j-2v]+ w,dp[i-1][j-3v]+2w,...);
进一步可以得到：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w)
那么我们按照套路，写一下多重背包的dp[i][j]
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2v]+2w,dp[i-1][j-3v]+3w,...,dp[i-1][j-sv]+sw);
dp[i][j-v]=max( dp[i-1][j-v], dp[i-1][j-2v]+ w,dp[i-1][j-3v]+2w,...,dp[i-1][j-v-(s-1)v]+(s-1)w,dp[i-1][j-sv]+(s+1)w);
观察dp[i][j] 和 dp[i][j-v] 可知，dp[i][j] 并不能直接用 dp[i][j-v]来求得（因为项数不同）。
但是，如若仔细观察一下，还是可以发现规律的：
dp[i][j] 的最大值，取决于dp[i-1][j] 和它前面s个dp[i-1][r]
也就是下图所示：
那么对于每个下标，我们只需要利用滑动窗口进行遍历，求最大值即可！！！
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20005;
int n,m; //n表示物品种数，m表示背包容量
int dp[N],q[N],g[N];//dp[i]表示体积为i时，最大价值。q[]是优先队列（用于滑动窗口的存放），存的是下标。g[]是拷贝数组，用于记录dp[i-1]这一行（把f[i][j]压缩到dp[j]之后，由于滑动窗口需要从前往后遍历，所以无法利用从后往前遍历的思想来处理f[i-1][]的数据。就用g[],把它记录下来。）
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
memcpy(g,dp,sizeof dp); //拷贝数组
for(int j = 0;j<v;j++) //这里j表示遍历到的体积k一直减去物品的体积v的余数（0<= j < v)
{
int hh=0,tt=-1; //表示队列的头和尾
for(int k=j; k<=m; k+=v) //k表示体积（下标），每次 += v（也就是新加一个物品）
{
if(hh<=tt && k-q[hh]+v>(s+1)*v) //如果队列不空，且队列长度大于 s+1 (注意，单位长度是v)，就把队列后移。
hh++;
if(hh<=tt) //如果队列不空，就求dp[k]
dp[k] = max(dp[k],g[q[hh]]+(k-q[hh])/v *w); //dp[k] 是滑动窗口的最大值（头部，也就是g[q[hh]]，还要加上(k-q[hh])/v *w，也就是后面的偏移量）
while(hh<=tt && g[q[tt]]<g[k]-(k-q[tt])/v*w) //如果队列不空，且队尾小于下一个数，那么要把队尾替换掉
tt--;
q[++tt]=k; //更新队尾
}
}
}
cout<<dp[m];
return 0;
}
四、分组背包
原题链接：9. 分组背包问题 - AcWing题库
因为每组只能选择一个，这一点和01背包是有点像的，下面给出代码及优化
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N][N]; //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N]; //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;
int 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(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
}
优化代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N];
int n, m;
int v[N][N], w[N][N], s[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 1; 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 = 1; k <= s[i]; k++)
{
if (j >= v[i][k])
{
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
}
}
}
}
cout << dp[m];
return 0;
}
五、二维费用背包问题
原题链接：1022. 宠物小精灵之收服 - AcWing题库
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k;
int dp[N][N]; //因为既要考虑收服精灵所消耗的精灵球的个数，又要考虑收服精灵所受到的伤害，所以要用二维数组表示，dp[i][j]表示最多消耗i个精灵球（可能不到i），最多收到j个伤害（可能不到j）时，所能收服的小精灵的最大数量
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= k; i++)
{
int num,hurt;
cin >> num >> hurt;
for (int a = n; a >= num; a--) //因为对每个精灵只能选择收服或者不收服，所以可以利用01背包的思想（逆序优化）
{
for (int b = m; b >= hurt; b--)
{
//if(dp[a][b] < dp[a - num][b - hurt] + 1)
dp[a][b] = max(dp[a][b], dp[a - num][b - hurt] + 1);//
}
}
}
//输出最多能收服的小精灵的数量
cout << dp[n][m-1] << " "; //注意这里，为什么要输出m-1？因为使得皮卡丘体力小于等于0的野生小精灵也不会被收服，所以最多只能消耗m-1的体力
int i;
for ( i = 0; i <= m; i++) //当最多使用n个小精灵球时，找到能收服最多个小精灵个数 的最小的伤害。
{
if (dp[n][i] == dp[n][m - 1])
break;
}
cout <<m - i << '\n';
return 0;
}
六、有依赖的背包
原题链接：10. 有依赖的背包问题 - AcWing题库
树型结构的分组背包
#include<bits/stdc++.h>
using namespace std;
const int N = 1110;
int n,m;
int v[N],w[N]; //分别表示体积和价值
vector<int> g[N]; //vector数组，用于表示g[fa].push_back(i)；表示在fa节点下加入他的孩子节点
int root; //表示根节点
int dp[N][N]; //dp[i][j] ，表示以i节点为根节点，选取他下面节点的体积，使得体积之和不超过j时，的最大价值
int dfs(int x) //x表示当前搜索的节点，（目的是以x为根节点，选取他的孩子节点）
{
for(int i = v[x];i<=m;i++) //以x为根节点，因为：如果选择一个物品，则必须选择它的父节点。所以可以把父节点所有体积初始化为w[x]
{
dp[x][i] = w[x];
}
for(int i = 0;i<g[x].size();i++) //接着遍历该节点的所有子节点。
{
int y = g[x][i];
dfs(y); //把每一个子节点都当做父节点，递归搜索，直到叶子结点，然后返回
for(int j = m;j>=v[x];j--) //j表示分给以x为根节点的树的体积。。。选取子节点的总体积不超过 m，因为该节点体积为v[x]，所以大于v[x]
{
for(int k = 0;k<=j - v[x] ;k++) //k表示选取的子树的体积范围，最大是j-v[x]。
{
dp[x][j] = max(dp[x][j], dp[x][j-k] + dp[y][k]);
}
}
}
}
int main()
{
cin>>n>>m;
int fa;
for(int i = 1;i<=n;i++)
{
cin>>v[i]>>w[i]>>fa;
if(fa == -1)
{
root = i;
}
g[fa].push_back(i);
}
dfs(root); //以根节点为起始点，开始搜索。
cout<<dp[root][m];
return 0;
}
七、背包问题求方案数
原题链接：11. 背包问题求方案数 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int dp[N]; //dp[j]表示体积不超过j时的最大价值
int res[N]; //res[j] 表示体积不超过j时能得到最大价值的方案数
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
}
for(int i = 0;i<=m;i++)
res[i]=1;
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= v[i]; j--)
{
int value = dp[j - v[i]] + w[i];
if (value > dp[j]) //说明value才是最大价值，所以res[j]此时的最大价值的方案数就是value对应的res[]也就是res[j-v[i]]
{
dp[j] = value;
res[j] = res[j - v[i]];
}
else if (value == dp[j]) //如果value==dp[j],说明j 和 j-v[i]对应的最大价值是一样的，也就是说他们都是能够达到最大价值的方案，所以要加起来（注意取模）
{
res[j] = (res[j] + res[j - v[i]]) % mod;
}
}
}
cout << res[m]%mod;
return 0;
}
八、背包问题求具体的方案
原题链接：12. 背包问题求具体方案 - AcWing题库
因为要保留每一次更新状态时的方案，也就是第一层循环的 i ，所以我们就不能把dp数组进行一维优化了。
至于为什么dp时，第一层循环要倒着来，我也没有想到如何定量的解释，下面来定性的分析一下：
因为dp取max时会实时更新的，也就是说，当前面的和后面的数都满足条件时，dp会保留后面的值。
因为我们要求的是字典序最小的一个方案。肯定是想要dp保留第一个满足的方案。所以我们就把它倒着遍历： for(int i = n;i>=1;i--) 这样的话，靠前面的dp[i][] 保留的就是最先满足的方案（也就保证了字典序最小）
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
}
for (int i = n; i >= 1; i--)
{
for (int j = 0; j <= m; j++)
{
dp[i][j] = dp[i + 1][j];
if (j >= v[i])
{
dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
}
}
}
int j = m;
for (int i = 1; i <= n; i++)
{
if (j >= v[i] && dp[i][j] == dp[i+1][j-v[i]]+w[i]) //如果可以选择第i个，并且决定选择了第i个，那么就把 i 输出
{
cout << i << " ";
j -= v[i];
}
}
return 0;
}
