动态规划法和回溯法求0-1背包问题 - CSDN文库

动态规划法

0/1背包问题

5星 · 超过95%的资源需积分: 10 166 浏览量更新于2023-06-23 4 收藏 117KB DOC 举报

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

领优惠券(最高得80元）

资源详情

资源推荐

《算法设计与分析》实验报告

学号：姓名：

日期：得分：

一、实验内容：

用回溯法求解 0/1 背包问题

注：给定种物品和一个容量为的背包，物品的重量是，其价值为，

背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的

总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：

1.回溯法求解背包问题：

1）基本思想：

回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断

地利用限界函数(bounding function)来处死那些实际上不可能产生所

需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生

成法称为回溯法。

对于有 n 种可选物品的 0/1 背包问题，其解空间由长度为 n 的 0-1

向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是

一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就

进入右子树搜索。

2）复杂度分析：

回溯法求解 0/1 背包

问题的时间复杂度为：。

空间复杂度：有个物品，即最多递归层，存储物品信息就是

一个一维数组，即回溯法求解 0/1 背包问题的空间复杂度为。

2.以动态规划法验证：

1）基本思想：

令表示在前个物品中

能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：

按照下述方法来划分阶

段：第一阶段，只装入前 1 个物品，确定在各种情况下的背包能够得到

的最大价值；第二阶段，只装入前 2 个物品，确定在各种情况下的背包

1

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

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

XACKWXl

粉丝: 3
资源: 10

会员权益专享

图片转文字

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

最新资源

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