#学习记录# 算法-动态规划-背包九讲(一）

vlambda
2020-03-26

#学习记录# 算法-动态规划-背包九讲(一）

这里是蓝色背包客的私人空间，只用来记录看到的和学到的，如果有幸被你点进来，也欢迎你留言说出自己的想法

第三次的内容关键词是：算法、动态规划、背包九讲

#Episode 3#

0 1

01背包问题

01背包问题：N个物品，每个物品有对应的价值vi和容量wi，有一个容量为V的背包，每个物体只能用一次，挑出物体使得物体的总容量不超过V，求可获得的最大价值。

基础方法：2维动态规划

重要变量：f[i][j]前i个物体，在总容量不超过j的情况下的最大价值

状态转移方程：

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

两种情况分析：

1）放入第i个物体，则在第i-1个物体时，要流出第i个物体的容量

2）不放入第i个物体，则在第i-1个物体时，满足条件总容量小于等于j即可

#include <iostream>using namespace std;const int N = 1010;int n, m; //物品个数，重量限制int v[N], w[N]; //每个物体价值，每个物体重量int f[N][N]; //f[i][j]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 = 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 << f[n][m] << endl; return 0; }

优化：2维动态规划优化到1维动态规划

在二维动态规划的时候，发现f[i]只和f[i-1]相关，如果将i维度去掉，我们需要保证f[j-v[i]]是i-1个物体时的最大物品价值，如果直接对代码进行处理f[j] = max(f[j], f[j-v[i]])，f[j-v[i]]计算的其实是第i个物体j-v[i]的价值。为了保证j-v[i]是第i-1个的价值，所以变为了逆序处理，保证j-v[i]在第i个物体时还未被更新。

#include <iostream>using namespace std;const int N = 1010;int n, m;int v[N], w[N];int f[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--)  f[j] = max(f[j], f[j-v[i]]+w[i]); cout << f[m] << endl; return 0; }

0 2

完全背包问题

完全背包问题：N个物品，每个物品有对应的价值vi和容量wi，有一个容量为V的背包，每个物体可以用无限次，挑出物体使得物体的总容量不超过V，求可获得的最大价值。

优化方法：1维动态规划

重要变量：f[i]在总容量不超过i的情况下的最大价值

从01背包问题1维动态规划的转移

 for(int j = m; j >= v[i]; j--)   f[j] = max(f[j], f[j-v[i]]+w[i]);

改动为：

 for(int j = m; j >= v[i]; j--)      for(int k = 0; k*v[i] <= m; k++)  f[j] = max(f[j], f[j-k*v[i]] + k*w[i]);

k表示对于i物体的拿取次数，我们需要保证拿取多次i物体也不会超过j的范围。

但是再思考一下，在01背包的改动，为了保证j-v[i]未被计算，选择了逆序处理背包重量，但是因为完全背包问题的物品是可以无限次拿取的，所以我们其实是需要j-v[i]被更新过，而每一次的更新意味着又拿取了一次i物品，所以代码可以改动为

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

0 3

多重背包问题

多重背包问题：N个物品，每个物品有对应的价值vi和容量wi，有一个容量为V的背包，每个物体最多可以用ki次，挑出物体使得物体的总容量不超过V，求可获得的最大价值。

优化方法：1维动态规划

重要变量：f[i][j]前i个物体，在总容量不超过j的情况下的最大价值

状态转移方程：

f[j] = max(f[j], f[j-k*v[i]]+k*w[i])

k的取值就是第i个物品可以取的个数。

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

往期回顾

一起成长分享快乐

学习和积累不会停止

文章总结：动态规划是技术岗面试的常考点，背包问题只是动态规划的一个分支，01背包、完全背包、多重背包、分组背包、混合背包问题、二维费用背包、背包问题方案数、背包问题最优方案和有依赖的背包问题都被囊括在其中。内容很丰富，也有很多值得思考的地方。2维的动态规划确实可以解决绝大多数的问题，但是面试官往往会要求去优化方案，所以了解每一个问题如何从二维动态规划转化为一维动态规划也是有必要的。今天的内容只是第一次的总结，之后还会有更多针对动态规划的总结内容。

你点的每个赞，我都认真当成了喜欢