该叶结点相应的解为问题的最优解。Р在while循环内部,算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。Р函数Knapsack()完成对输入数据的处理。其主要任务是将各物品依其单位重量价值从达到小排好序。然后调用函数MaxKnapsack()完成对子集树的优先队列式分支限界搜索。Р 具体的实现代码在文件夹《分支限界法》中。Р时空效率分析Р穷举法:Р 对于一个有n个元素的集合,其子集数量为,所以,不论生成子集的算法效率有多高,穷举法都会导致一个的算法。Р递归法:Р 在递归法的算法体中有一个if判断中出现了两次递归调用比较大小所以它们之间的递归关系式可以大体表示为:,其中表示递归法的时间复杂度,C是常数。求解递归方程可以知道的量级为。所以递归法解0-1背包问题的时间复杂度为。递归法是耗费空间最多的算法,每次递归调用都需要压栈,导致栈的使用很频繁。Р动态规划法:Р 由于函数Knapsack中有一个两重for循环,所以时间复杂度为O[(n+1)x(m+1)].空间复复杂度也是O[(n+1)x(m+1)],即O(nm).Р回溯法:Р由于计算上界的函数MaxBoundary需要O(n)时间,在最坏情况下有个右儿子结点需要计算上界,所以解0-1背包问题的回溯法算法BackTrack所需要的计算时间为.Р限界分支法:Р 在使用限界分治法时,就是使用更好的限界剪枝函数使得不必要的解被剔除,但是在最坏情况下的解仍然是和回溯法是相同的。本算法中也是用到了计算上界的函数MaxBoundary需要O(n)的时间,而且在最坏情况下有Р个结点需要计算上界,所以在最坏情况下的时间复杂度仍然为。Р运行结果Р递归法输出结果:Р动态规划法输出结果:
全文预览
