【01背包】滚动数组优化实现一维01背包DP(对比朴素写法)

01背包

代码

背包问题的滚动数组优化版本建议在完全弄懂了普通的二维01背包问题后再进行食用，不然会出现消化不良的症状…

我们可以将背包问题中DP数组的下标看作成两个集合

下面对比两种不同实现方法的区别：

• 朴素二维DP版本

  • 使用dp[不超过i的物品集合][不超过j的背包集合]。
  • 我们会发现，每次使用的[不超过第i个物品的集合]只会是i和i-1，再往前的集合在后续的计算都不会被使用，所以可以采用滚动数组的思想，不断的更新一个一维数组来达到相同的目的。
  • 同时，我们每次会对每一个物品寻找所有[不超过j的背包的集合]，如果背包放不下这个物品，直接继承没有放i物品的状态即可，也就是[不超过i-1位物品]的集合。
  • 同时这里和优化版本的区别还在于遍历顺序，朴素版本不用考虑遍历顺序，但是优化版本需要注意。

  #include <iostream>
  using namespace std;
  // DP-normal-way
  
  const int N = 1010;
  int n, m;		//n件物品 m容量的背包 
  int v[N], w[N]; //每件物品的体积 价值 
  int f[N][N];	//f[i][j]不超过第i件物品 背包容量不超过j 
  
  /*
  4 5
  1 2
  2 4
  3 4
  4 5
  */
  
  int main() {
  	cin >> n >> m;
  	
  	for (int i = 1; i <= n; i++) {
  		cin >> v[i] >> w[i];			//输入体积 价值 
  	}
  	//f[0][0~m]默认为零，无需进行初始化
  	
  	for (int i = 1; i <= n; i++) {
  		for (int j = 1; j <= m; j++) {
  			if (j >= v[i]) f[i][j] = max(f[i-1][j], w[i] + f[i-1][j-v[i]]);
  			else f[i][j] = f[i-1][j];
  		}
  	} 	
  	
  	cout << f[n][m] << endl;	
  }
  

• 滚动数组优化版本 --> 一维DP(01背包问题终极写法)

  • dp[i][j]-->dp[j]删掉了i这个集合，相当于现在每次只存放了前一个物品的[背包不超过j]的最大值。
    • 比如第一次，dp[]存放的是不超过第一个物品的[背包不超过j] 的最大值。
    • 第二次在第一次的基础上进行更新，这里需要注意背包集合的遍历顺序，需要思考如果还是正序遍历会带来什么影响？
    • 没错，因为每次都要利用到之前的[背包不超过j]的集合，如果正序遍历，那么就会从小的背包开始更新，那么就会把上一次的背包最大值覆盖掉，遍历到后面，j大起来了，要使用上一次也就是[物品不超过i-1]的[背包不超过j]的集合来进行更新就会碰到滚动数组数据被覆盖了的问题。
    • 所以，需要注意的就是，要从大的背包开始遍历j，这样就可以避免dp[背包容量<j]被覆盖掉，进行滚动的更新。

  #include <iostream>
  // 01背包1维写法 
  
  const int N = 10010;
  int n, m;	//物品个数  背包容量
  int v[N], w[N];	//每个物品的：体积 价值
  int dp[N];	//优化前：不超过i的物品的体积和不超过j的背包 --> 优化后： 不超过i件物品  -->最大价值 
  /*输入数据不变： 
  4 5
  1 2
  2 4
  3 4
  4 5
  */
  using namespace std;
  
  int main() {
  	cin >> n >> m;
  	for (int i = 0; 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] << endl;
  }