用回溯法、蛮力法解决01背包问题_动态规划法求01背包问题 - CSDN文库

5星 · 超过95%的资源需积分: 20 84 浏览量更新于2023-03-03 评论 5 收藏 71KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

算法分析之 0/1 背包问题

1. 0/1 背包问题定义及应用背景

 背包问题属于  难解问题类，背包问题可以简单描述为：一个旅行者有一个最

多能用  公斤的背包，现在有  件物品，它们的重量分别是 ，，它们的价

值分别为 。若每种物品只有一件求旅行者能获得最大总价值。

 背包问题可应用的实例很多，比如有  项可投资的项目，每个项目需要投入资金

，可获得利润为 ，现有可用总资金数为 ，应选择哪些项目来投资可获得最大利润。

2. 用回溯法解决 0/1 背包问题

2.1 回溯法定义

回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空

间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一

结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结

点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先

的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都

已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以

结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组

合数较大的问题。

、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解

空间应到少包含问题的一个（最优）解。

、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结

点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也

成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结

点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深

方向移动，则当前扩展结点就成为死结点。。此时，应往回移动（回溯）至最近的一个活

结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间

中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

运用回溯法解题通常包含以下三个步骤：

（）针对所给问题，定义问题的解空间；

（）确定易于搜索的解空间结构；

（）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

回溯法解决背包问题的思想是：

（）



本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

评论6

wj312312312

2013-04-12

谢谢好人啊。能用

PeachblossomImmortal

粉丝: 0
资源: 1

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈