Acwing算法基础课第五讲总结
背包问题
AcWing-2 01背包问题
状态表示:
f[i,j]
集合:
在前i件物品中,选择总体积不超过j的物品的所有选择方案
属性:
集合中所有选择方案中,价值最大的方案的价值具体值
状态计算:
集合划分为:包含了第
i
件物品f[i-1,j-v[i]]+w[i]
和不包含第i
件物品f[i-1,j]
状态转移方程:
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
朴素做法:
复杂度为$O(n^2)$。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int v[maxn], w[maxn];
int f[maxn][maxn];
int main(void)
{
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++) //在前i个物品中选择
{
//枚举体积j时,由于f[i,0]都是0,所以从0和1开始枚举都是一样的
for(int j = 0; j <= m; j++) //且总体积不超过j的情况下的所有取法
{
f[i][j] = f[i-1][j]; //先将状态转移再考虑能否装下第i个物品
if(j - v[i] >= 0) //能装下第i个物品,装下后总体积相应的要减小v[i],同时总价值加上w[i]
f[i][j] = max(f[i-1][j-v[i]] + w[i], f[i-1][j]);
}
}
cout << f[n][m] << endl;
return 0;
}
优化做法:
在代码上面做等价变形即可,变形之后一定要保证状态转移方程和原来是等价的。
首先注意到,由于第一维只使用到了i和i-1这两个下标,那么可以优化为滚动数组,即一维的两层数组交替使用
又,注意到在状态转移方程中f[i]
更新用到的状态都只和f[i-1]
有关,也就是只要保证i
是依次枚举到n
就可以覆盖到所有状态了,所以不需要存储i
这一维
而由于在枚举j
的时候,显然有能够放进背包的物品的总体积始终不会超过j
,即v[i]<=j
恒成立,v[i]
的值只会在j的一侧。
那么直接用一维数组来存储总体积不超过j
的物品的总价值即可
但需要注意的是,由于去掉i
那一维之后,新的状态转移方程用到的都是当前的i
这一维的状态,和原状态转移方程不等价
要使得新的代码和原来的状态转移方程等价的话,那么只有逆序枚举j
这样才能保证是用上一轮即i-1
轮的状态来更新当前的状态
比如,更新f[7]
时,用的就是第i-1
轮时的f[4]
的值,当前的f[4]
(也就是第i
轮)的值,会在更新完f[7]
之后再算
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int v[maxn], w[maxn];
int f[maxn];
int main(void)
{
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 = m; j >= v[i]; j--)
f[j] = max(f[j-v[i]] + w[i], f[j]);
cout << f[m] << endl;
return 0;
}
AcWing-3 完全背包问题
状态表示:
f[i][j]
集合:
在前i个物品中选择总体积不超过j的物品的所有选法
属性:
所有选法价值的最大值
状态计算:
集合划分为,第i个物品取了0~k个(k的范围是0到正无穷,但由于背包容积有限,所以k的值为有限值)。
状态转移方程:
f[i][j] = max(f[i-1][j-k * v[i]] + k * w[i])
朴素做法:
这里由于每种物品有无限个,所以还需要多一重循环来枚举第i个物品取了多少个,复杂度为$O(n^3)$,从而朴素做法会超时。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn];
int main(void)
{
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;
return 0;
}
时间复杂度优化:
由状态转移方程f[i][j]
和f[i][j-v[i]]
展开并比较它们
可以得出简化后的等价状态转移方程f[i][j]=max(f[i-1][j], f[i][j-v[i]]+w[i])
从而可以去掉枚举每种物品取的个数k的那层循环,使得时间复杂度降至平方级别
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn];
int main(void)
{
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++)
{
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;
return 0;
}
空间复杂度优化:
类似于01背包的思路,但是注意两者的区别,这里的j可以不用逆序枚举
因为这里的状态转移方程中对应用到的就是第i轮的状态,而顺序枚举对应的就是用第i轮的状态去更新的
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[maxn];
int v[maxn], w[maxn];
int main(void)
{
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;
return 0;
}
AcWing-4 多重背包问题 I
状态表示:
f[i][j]
集合:前i个物品中选择总体积不超过j的所有选法。
属性:
所有选法价值最大值。
状态计算:
集合划分为,第
i
种物品取了0~s[i]
件。 从而状态转移方程为
f[i][j] = max(f[i-1][j - k*v[i]] + k*w[i]
(注意k的取值范围和完全背包问题不同)。朴素做法:
复杂度为$O(n^3)$。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn], s[maxn];
int main(void)
{
int n, m;
cin >> 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 = 0; 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 - k*v[i]] + k*w[i]);
cout << f[n][m] << endl;
return 0;
}
AcWing-5 多重背包问题 II
即用2的各幂次项来凑出
s[i]
。优化做法(时间复杂度为$O(n^2logs)$:
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 25000; //转化后的物品个数为N*logs
int f[maxn];
int v[maxn], w[maxn];
int main(void)
{
int n, m;
cin >> n >> m;
int cnt = 0; //存放转化后的物品个数
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) //2的幂次项凑不了的部分
{
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;
return 0;
}
AcWing-9 分组背包问题
状态表示:
f[i][j]
集合:
只从前
i
组物品当中选,且总体积不超过j
的情况下的所有选法。属性:
所有选法价值的最大值。
状态计算:
集合划分为,第
i
组物品中选了0
个或选了第k
个。从而状态转移方程为:
f[i][j] = max(f[i-1][j], f[i-1][j-v[i][k]] + w[i][k])
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110; //转化后的物品个数为N*logs
int f[maxn];
int v[maxn][maxn], w[maxn][maxn], s[maxn];
int main(void)
{
int n, m;
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--) //注意这里要写成大于等于0
for(int k = 1; k <= s[i]; k++)
if(j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}
线性DP
AcWing-898 数字三角形
f[i][j]
集合:
所有从起点走到点
(i, j)
的路径走法。属性:
所有走法中,路径上的数字之和最大值。
状态计算:
集合划分为,走到
(i, j)
这个数的位置在左上和右上两种情况。从而递推方程为,
f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j])
。#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 510;
const int inf = 2e9;
int f[maxn][maxn];
int a[maxn][maxn];
int main(void)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
//初始化的时候注意把数字三角形左右两边的空隙部分也初始化为负无穷
for(int i = 0; i <= n; i++)
for(int j = 0; j <= i + 1; j++)
f[i][j] = -inf;
f[1][1] = a[1][1];
for(int i = 2; i <= n; i++)
for(int j = 1; j <= i; j++)
f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]);
int res = -inf;
for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
AcWing-
区间DP
计数类DP
数位统计DP
状态压缩DP
树形DP
记忆化搜索
AcWing-901 滑雪
f[i][j]
表示从点(i, j)
出发的所有能走的路径,而它存储的就是从它出发的所有路径中最长的路径的长度。递推方程为
f[i][j] = f[i+dx][j+dy] + 1
。也就是将集合划分为从该点朝上下左右四个方向走下一步的四种路径,而状态计算的方式就是先得到去掉当前走到这一个点这一步,只看从下一个点出发走的路径的最大值,最后再加上走到这个点的路径长度
1
,那么最后得到的就是从点(i, j)
走的所有路径长度的最大值。这里是先用到的后面的状态,所以递归求解显得很方便。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 310;
int a[maxn][maxn];
int f[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int r, c;
int dp(int x, int y)
{
int &v = f[x][y]; //简化代码,记得加&
if(v != -1) return v; //走过的点不计入路径长度,直接结束这层递归
v = 1; //走到当前这个点,路径长度加1
for(int i = 0; i < 4; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if(tx >= 1 && tx <= r && ty >= 1 && ty <= c && a[tx][ty] < a[x][y])
{
//递推方程的体现
v = max(v, dp(tx, ty) + 1);
}
}
return v; //当前点周围已经没有能够继续滑下去的点,结束这层递归
}
int main(void)
{
scanf("%d %d", &r, &c);
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
scanf("%d", &a[i][j]);
memset(f, -1, sizeof(f)); //标记是否达到过该点,并存储路径长度
int res = 0;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
res = max(res, dp(i, j));
printf("%d\n", res);
return 0;
}
参考资料
AcWing-2 01背包问题参考资料1
AcWing-2 01背包问题参考资料2
AcWing-900 整数划分参考资料