0-1背包问题（回朔法搜索子集树）_背包问题搜索树怎么画

作者：2023面试高手 | 2024-03-29 02:09:32

踩

背包问题搜索树怎么画

将解空间用一颗完全二叉树表示，用回朔法搜索这颗树：

解法1：建立了一个完全二叉树（称子集树），结点中带有需要的信息，深度优先遍历这颗二叉树（递归方法），

找到最优解。

困难：如何记录当前的路径？

解决方案：1、设置一个栈

2、在递归调用“深度优先遍历左子树”之前，将0压入栈；在递归调用“深度优先遍历右子树”之前，将1压入栈

3、当递归调用出来后，将栈顶元素弹出

这样到了页结点的时候，栈中的元素就是一个解

解法2：（巧妙）不需要建立树的代码，只需要用一个数组存放访问路径，核心代码如下：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/333087