当前位置:首页 >> 计算机硬件及网络 >>

回溯法解决01背包问题


回溯法是一个既带有系统性又带有跳跃性的搜索算法。 它在包含问题的所有解的解空间树中按照 深度优先的策略,从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时,总是先判断 该节点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该节点为根的子树的系统搜索, 逐层向其原先节点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。 运用回溯法解题通常包含以下三个步骤: ? ? ? 针对所给问题,定义问题的解空间; 确定易于搜索的解空间结构; 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;

在 0/1 背包问题中,容量为 M 的背包装载。从 n 个物品中选取装入背包的物品,物品 i 的重量为 Wi,价值为 Pi。最佳装载指装入的物品价值最高,即∑PiXi(i=1..n)取最大值。约束条件为∑WiXi ≤M 且 Xi∈[0,1](1≤i≤n)。 在这个表达式中,需求出 Xi 的值。Xi=1 表示物品 i 装入背包,Xi=0 表示物品 i 不装入背包。 ? ? 即判断可行解的约束条件是:∑WiXi≤M(i=0..n),Wi>0,Xi∈[0,1](1≤i≤n) 目标最大值:max∑PiXi(i=0..n-1),Pi>0,Xi=0 或 1(0≤i<n)

0/1 背包问题是一个自己选取问题,适合于用子集树表示 0/1 背包问题的解空间。在搜索解空 间树时,只要左儿子节点是一个可行节点,搜索就进入左子树,在右子树中有可能包含最优解才 进入右子树搜索,否则将右子树剪去。 程序分析: 将物品个数,每个物品体积/价值输入,计算总物品体积 S,输入背包体积 V,如果 V<0 或者 V>S 则前置条件错误,即背包体积输入错误,否则顺序将物品放入背包。假设放入前 i 件物品, 背包没有装满,继续选取第 i+1 件物品,若该物品“太大”不能装入,则弃之继而选取下一件 直到背包装满为止;如果剩余物品中找不到合适物品以填满背包,则说明“刚刚”装入的第 i 件

物品不合适,应将 i 拿出,继续从 i+1 及以后的物品中选取,如此重复,直到找到满足条件的 解。 回溯求解,物品放入的规则是“后进先出”,所以要用栈存储符合条件的解。

剪枝(限界)函数 设当前剩余物品价值总和为 r,当前结点 x 价值为 cp,当前 x 结点上界函数值为 bp。L 为当前 已搜索到的答案结点中受益的最大值,当 cp+r=bp<L 时可剪去以 X 为根的子树。 计算右子树中解上界方法是将剩余物品按单位重量价值排序, 一次放入物品直至装不下为止, 再 装入部分未装入物品直至装满背包,由此得到的价值是右子树解上界。 递归方式:

是否已经拿完 所有物品? 否



打印输出 第i个物品能否 放入背包? 能

放入还是不放入 放入 不能 第i个物品放 入操作

不放入 递归第i+1个 物品

开始

当前物品序号i超过 物品总数?



打印输出

结束

否 背包是否容得 下第i个物品? 是 是否剪枝? (可以没有该 判断) 否



放入第i个物品 否 对第i+1个物品 状态判断(递 归)

取出第i个物品

对第i+1个物品 状态判断(递 归)

顺序方式: 无剪枝函数:
开始

所有物品都 已放入包内? (i<n)



打印

否 拿出最后放入 的物品 当前物品i能否 放入包内? 是 将当前物品i 放入包内 背包内还有物 品? 不能

没有

结束

i++



有剪枝函数:

开始

所有物品都 已放入包内? (i<n)



打印



当前物品i能否 放入包内? 是 将当前物品i 放入包内

不能

后续物品价值能 否超过当前最高 价值?



拿出最后放入 的物品



背包内还有物 品?

没有

结束

i++



AbsBacktracking +Backtracking() #Printing()

<<数据类型>> Obj

Backtracking_Recursion

Backtracking_Nonrecursion


相关文章:
回溯法求01背包问题
回溯法01背包问题 - 实验题目 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值 为 vi,0/1 背包问题是如何选择装入背包的物品(物品不可...
动态规划与回溯法解决0-1背包问题
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描述: 有 n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的...
回溯算法解决0-1背包问题
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:回溯算法....
用回溯法解决0-1背包问题
回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决...文档贡献者 heaven龙晓梅 贡献于2018-07-01 1 /2 相关文档推荐 ...
算法分析与程序设计动态规划及回溯法解01背包问题...
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
回溯法实验(0-1背包问题)
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
蛮力法、动态规划法、回溯法和分支限界法求解01背...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注:0/1 背包...
回溯法01背包问题
回溯法01背包问题 - 核心源代码 #include &lt;iostream.h&gt; struct bag { double w; double cw,cp,bestp; }; struct goo...
回溯法解0-1背包问题实验报告
实验4 一 、实验要求 回溯法解 0-1 背包问题 1.要求用回溯法求解 0-1 ...文档贡献者 我是伊大头 贡献于2018-07-01 1 /2 相关文档推荐 ...
回溯法求0-1背包问题
回溯法求0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
更多相关标签: