算法分析之 0_1背包问题回溯法
用回溯法解0_1背包问题时,会用到状态空间树。在搜索状态空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索,否则将右子树剪去。设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r≤bestp时,可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界,用此值来剪枝。为了便于计算上界,可先将物品依其单位重量价值从大到小排序,此后只要顺序考察各物品即可。在实现时,由MaxBoundary函数计算当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录了解
用户评论
推荐下载
-
求解0_1背包问题的改进人工鱼群算法研究
人工鱼群算法应用到求解0-1背包问题上时,可以有效的提高求解精度和速度。
19 2020-07-16 -
0_1背包问题贪心算法C语言源程序
0-1背包问题(贪心算法)C语言源程序.物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。
38 2019-05-15 -
模拟退火算法解决0_1背包问题的实现
背包问题,是指从n件不同价值、不同重量物品中按一定的要求选取一部分物品,并使选中物品的价值之和为最大的问题。其形式化描述如下:给定一个物品集合s={1,2,…,n},物品i具有重量和价值。背包能承受的
36 2019-04-28 -
分支界限思想解0_1背包算法
Branch boundary thinking solution 0-1 knapsack algorithm
38 2019-06-28 -
四种算法写0_1背包
用回溯、分支限界、动态规划解0-1背包,与用贪心思想进行比较.
12 2019-04-28 -
0_1背包_动态规划算法
用动态规划算法解决0-1背包问题,希望可以帮到大家
30 2018-12-29 -
改进动态规划跳跃点之0_1背包问题python实现
这个是动态规划之跳跃点0-1背包问题,如果只是想要动态规划0-1背包问题求解代码,请到主页查看。18级学姐自主完成的算法作业,呕心沥血,基于四舍五入等于0基础的python实现,如果在语言规范上存在不
26 2019-05-06 -
回溯法背包问题和装载问题
回溯法 背包问题和装载问题 书上的算法。
50 2019-01-09 -
0_1背包问题四种解法.pdf
这个文档描述了背包问题的四种解法,可以帮助我们更加增加对背包问题的描述
9 2020-09-21 -
一个0_1背包问题的实现
这个是背包问题中的o/1背包问题的贪心算法实现程序,程序能够运行,已经测试过。希望能对大家有所帮助
19 2019-09-03
暂无评论