0/1背包问题（蛮力、动态规划、回溯、分支限界法）_蛮力法01背包问题 - CSDN文库

0/1背包问题

动态规划法

分支限界法

5星 · 超过95%的资源需积分: 35 154 浏览量更新于2023-03-16 评论 41 收藏 162KB DOC 举报

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

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

学号：姓名：

日期：得分：

一、实验内容：

分别用蛮力法、动态规划法、回溯法和分支限界法求解  背包问题。

注： 背包问题：给定种物品和一个容量为的背包，物品的重

量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装

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

入背包两种选择。

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

1.蛮力法求解 0/1 背包问题：

1）基本思想：

对于有  种可选物品的  背包问题，其解空间由长度为  的 

向量组成可用子集数表示。在搜索解空间树时，深度优先遍历，搜索

每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次

得到的装入总价值，然后记录遍历过的最大价值。

2）复杂度分析：

蛮力法求解  背包

问题的时间复杂度为：。

2.动态规划法求解 0/1 背包问题：

1）基本思想：

令表示在前个物品中

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

按照下述方法来划分阶

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

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

能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为

的背包中装入个物品时取得的最大价值。

2）复杂度分析：

动态规划法求解

 背包问题的时间复杂度为：。

1

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

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

评论25

zhouchao121

2014-02-10

正在做相关的课设，很有帮助！谢谢。

XACKWXl

粉丝: 3
资源: 10

会员权益专享

图片转文字

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

最新资源

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