devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

回溯法解决01背包问题_回溯算法与动态规划基于背包问题的浅析

作者：Cpp五条 | 2024-03-29 01:57:21

赞

踩

01背包问题回溯法时间复杂度

经典问题描述：有n 个物品，它们有各自的重量，现有给定容量w的背包，如何让背包里装入的物品具有最大的重量？

回溯算法解背包问题

假设我们有五个物品，重量分别为2,3,3,7,5，背包所能容纳的最大重量为10.怎么解呢？最笨的方法就是使用回溯算法穷举所有的情况，直到遇到临界情况，递归树如下：

eec129a1e12f01a57878a558ea55c597.png

8367de64a48c12a06972a8d6a4c2c731.png

​

其中每个节点f(i,cw),代表决策第i个物品是否放入，并且此时背包里所有物品总重为cw。因此，回朔算法的时间复杂度成指数增长，并且包含了打量了重复运算（比如两个f(2,2））。如果我们的物品i遍历完毕，或者cw超出背包的总重，即临界退出条件，因此我们可以给出回溯算法的代码（物品重量用数组items表示，w代表背包容量，maxW存储当前最大重量，这些自己设置）：

  1. void knapsackProblem::backTracing(int i, int cw)
  2. {
  3. 	if (i == n || cw == w) {//i==n代表所有物品加载完毕，cw==w代表背包填满，则直接跳出
  4. 		if (cw > maxW) maxW = cw;
  5. 		return;
  6. 	}
  7. 	//装与不装第i个物品两种情况
  8. 	backTracing(i + 1, cw);//选择不装第i个物品
  9. 	if (cw + items[i] <= w) {//如果第i个物品能放进去，就选择装第i个物品
  10. 		backTracing(i + 1, cw + items[i]);
  11. 	}
  12. }

可以看出，回溯算法对决策时的每种情况都进行了分析，时间复杂度为2^n，这实在太多庞大（比如n为10000时）。我们分析复杂度如此高的原因是回朔算法进行了大量重复的运算，如果我们能设置一个备忘录来避免这些重复的运算，那岂不是妙哉？既然每个节点的两个参数是物品次序和当前背包重量，我们可以采用一个bool类型的二维数组来记忆是否已经进行了相关运算。

  1.     bool** mem = new bool*[n];
  2. 	for (int i = 0; i != n; ++i) {
  3. 		mem[i] = new bool[w + 1];
  4. 	}
  5.  
  6.     for (int i = 0; i != n; ++i) {
  7. 		for (int j = 0; j != w + 1; ++j) {
  8. 			mem[i][j] = false;
  9. 		}
  10. 	}

然后给出加载了备忘录的回溯算法：

  1. void knapsackProblem::backTracing(int i, int cw)
  2. {
  3. 	if (i == n || cw == w) {//i==n代表所有物品加载完毕，cw==w代表背包填满，则直接跳出
  4. 		if (cw > maxW) maxW = cw;
  5. 		return;
  6. 	}
  7. 	if (mem[i][cw]) return;//如果这个节点运算过，则直接返回
  8. 	mem[i][cw] = true;//否则将这个节点的运算状态设为true
  9. 	//装与不装第i个物品两种情况
  10. 	backTracing(i + 1, cw);//选择不装第i个物品
  11. 	if (cw + items[i] <= w) {//如果第i个物品能放进去，就选择装第i个物品
  12. 		backTracing(i + 1, cw + items[i]);
  13. 	}
  14. }

8367de64a48c12a06972a8d6a4c2c731.png

这样就避免了那些复杂的运算，用空间换来了时间，这其实就有点类似于动态规划的思想方法了。但是回溯算法尚且有局限性（比如节点有三个参数或者四个参数时很难使用备忘录），接下来我们看看动态规划如何实现背包问题。

动态规划解背包问题

其实上面带有备忘录的回朔算法已经十分接近动态规划了，动态规划中我们通过上一层的状态来决策下一层的状态，并且只统计那些不重复的节点，例如我们由f(1,0)和f(1,2)推出f(2,0),f(2,2),f(2,5).这样可以保证每层的节点数永远不会超过cw的最大值，即w（背包容量）.整个过程依然可以通过一个表格来进行表示：

2f68c434c46647bc73bd5e1d2ef5cef7.png

8367de64a48c12a06972a8d6a4c2c731.png

​

8dfdeee14a0a40ff73a9b9c3c7042f5f.png

8367de64a48c12a06972a8d6a4c2c731.png

​

第一次决策 第二次决策

fb56ddaad582bf8d20dad95a591b71cf.png

8367de64a48c12a06972a8d6a4c2c731.png

​

0bf5b8b5d6274a68b9dcaf08b563e98e.png

8367de64a48c12a06972a8d6a4c2c731.png

​

第三次决策 第四次决策

ed2647483eef12cfcacc4d91ba6bfce3.png

8367de64a48c12a06972a8d6a4c2c731.png

​

第五次决策

注意：2列应当置1

分析：第一次决策是否装第一个物品，其重量为2，所以决策完毕有总重0和2两种情况。

第二次决策第二个物品，其重量为3，我们只需要从第一行分析即可，不装第二个物品时，摘抄第一行即可，装第二个物品时就分别加3.

以此类推~~

决策完毕只需要取出最后一行对应的最大重量即可。

因此，动态规划算法也需要一个辅助的二维数组来存储节点状态。

  1.     bool** states = new bool*[n];
  2. 	for (int i = 0; i != n; ++i) {
  3. 		states[i] = new bool[w + 1];
  4. 	}
  5. 	for (int i = 0; i != n; ++i) {
  6. 		for (int j = 0; j != w + 1; ++j) {
  7. 			states[i][j] = false;
  8. 		}
  9. 	}
  10.     //第一行需要特殊处理，设置为true；
  11. 	states[0][0] = true;
  12. 	states[0][items[0]] = true;

8367de64a48c12a06972a8d6a4c2c731.png

因此动态规划的代码如下，不是很复杂：

  1. int knapsackProblem::dynamicProgramming(int * items, int n, int w)
  2. {
  3. 	for (int i = 1; i != n; ++i) {
  4. 		//不装第i个物品
  5. 		for (int j = 0; j <= w; ++j) {
  6. 			if (states[i - 1][j] == true) states[i][j] = true;
  7. 		}
  8. 		//装第i个物品
  9. 		for (int j = 0; j <= w - items[i]; ++j) {
  10. 			if (states[i - 1][j] == true) states[i][j + items[i]] = true;
  11. 		}
  12. 	}
  13.     //输出可装最大重量，即在最后一行从后往前遍历
  14. 	for (int i = w + 1; i >= 0; --i) {
  15. 		if (states[n - 1][i] == true)return i;
  16. 	}
  17. 	return 0;
  18. }

8367de64a48c12a06972a8d6a4c2c731.png

此算法的时间复杂度为n*w,空间复杂度也为n*w。

有没有办法对空间复杂度进行改进呢，答案是有的，因为此二维数组有很多重复的地方，我们完全可以用一维数组代替。

  1. int knapsackProblem::dynamicProgramming1(int * items, int n, int w)
  2. {
  3. 	bool* states = new bool[w + 1];
  4. 	for (int i = 0; i != w + 1; ++i) {
  5. 		states[i] = false;
  6. 	}
  7. 	states[0] = true;
  8. 	for (int i = 1; i != n; ++i) {
  9. 		//因为如果不装第i个物品，此一维数组不会有任何变动，所以我们直接考虑装第i个物品
  10. 		for (int j = w - items[i]; j >= 0; --j) {
  11. 			//为什么要从大往小便利呢？因为下面的循环体是前值影响后值
  12. 			if (states[j] == true) states[j + items[i]] = true;
  13. 		}
  14. 	}
  15. 	for (int i = w; i >= 0; --i) {
  16. 		if (states[i] == true)return i;
  17. 	}
  18. 	return 0;
  19. }

8367de64a48c12a06972a8d6a4c2c731.png

背包问题的升级

对于上面的背包问题已经解决，可如果再增加一个限制条件呢？如：刚刚的问题只涉及背包容量和物品重量，可如果我们引入物品价值这一变量，对一组不同重量不同价值的物品，我们选择一些物品加入背包，在不超出背包最大容量的限制下，可装入背包物品的总价值最大是多少呢？

当然，我们依然可以使用笨重的回溯算法来解决这个问题，此时每个节点就有了三个参数分别为i(物品),cw(当前总重量),cv(当前总价值），具体实现代码如下：

  1. void knapsackProblem::backTracing(int i, int cw, int cv)
  2. {
  3. 	if (i == n || cw == w) {//i==n代表所有物品加载完毕，cw==w代表背包填满，则直接跳出
  4. 		if (cw > maxW) maxW = cw;
  5. 		return;
  6. 	}
  7. 	//装与不装第i个物品两种情况
  8. 	backTracing(i + 1, cw, cv);//选择不装第i个物品
  9. 	if (cw + items[i] <= w) {//如果第i个物品能放进去，就选择装第i个物品
  10. 		backTracing(i + 1, cw + items[i], cv + value[i]);
  11. 	}
  12. }

8367de64a48c12a06972a8d6a4c2c731.png

假设物品价值为 int* value ={3,7,5,2,6},照样画出递归树示意图如下(每个节点代表物品，目前总重，目前总价)：

ea74f200618c88856a9d0f6a2981d5f9.png

8367de64a48c12a06972a8d6a4c2c731.png

​

我们可以发现虽然暂时没见到重复的节点，可是对比f(2,2,7)和f(2,2,3),相同重量必然选择较高价值的，因此f(2,2,7)可以直接忽略不计。可是这又很难用备忘录来实现，那么动态规划如何解决这个问题呢？

依然借助二维数组，不过此时二维数不再用bool来表示，而用int代表每个状态的value值，初始化为-1.如下：

  1. v_states = new int*[n];
  2. 	for (int i = 0; i != n; ++i) {
  3. 		v_states[i] = new int[w + 1];
  4. 	}
  5. 	for (int i = 0; i != n; ++i) {
  6. 		for (int j = 0; j != w + 1; ++j) {
  7. 			v_states[i][j] = -1;
  8. 		}
  9. 	}
  10. 	states[0][0] = 0;
  11. 	states[0][items[0]] = value[0];

8367de64a48c12a06972a8d6a4c2c731.png

动态规划本身则和之前的算法大同小异，具体如下：

  1. int knapsackProblem::dynamicProgramming(int * items, int * value, int n, int w)
  2. {
  3. 	for (int i = 1; i != n; ++i) {
  4. 		//选择不装第i个物品
  5. 		for (int j = 0; j != w; ++j) {
  6. 			if (v_states[i - 1][j] >= 0) v_states[i][j] = v_states[i - 1][j];
  7. 		}
  8. 		//选择装第i个物品
  9. 		for (int j = 0; j <= w - items[i]; ++j) {
  10. 			if (v_states[i - 1][j] >= 0) {
  11. 				int v = v_states[i - 1][j] + value[i];
  12. 				if (v > v_states[i][j + items[i]]) {
  13. 					v_states[i][j + items[i]] = v;
  14. 				}
  15. 			}
  16. 		}
  17. 	}
  18. 	//寻找最大值
  19. 	int maxV;
  20. 	for (int j = 0; j <= w; ++j) {
  21. 		if (v_states[n - 1][j] > maxV) maxV = v_states[n - 1][j];
  22. 	}
  23. 	return maxV;
  24. }

8367de64a48c12a06972a8d6a4c2c731.png

当然，此种方法也可以优化一下空间复杂度，留给读者自己分析。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/333008
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号