论文部分内容阅读
从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。所以,对背包问题求解方法的研究无论是在理论上还是在实践中都具有一定的意义。论文中所做的主要工作如下：(1)运用经典算法求解0-1背包问题,并设计基于二表思想的混合算法。(2)提出空间复杂度改进的混合算法RKP算法求解0-1背包问题。RKP算法结合一般的动态规划算法和分治策略,能够在时间复杂度O(nC)情况下仅用O(C)的空间复杂度求解0-1背包问题。并且在不用回溯步骤的前提下,求得放入背包的物品。(3)将解决0-1背包问题的动态规划串行算法扩展到并行算法。分析表明：垂直划分表区域的的动态规划并行算法受物品重量的影响而导致处理器访问数据困难,系统带宽负担重和代码复杂；相比之下,水平划分表区域的动态规划并行算法具有较大的优势。对于每个处理器,每次处理的数据块的列大小为b’=(?)时(其中C为背包容量，p为处理器数目,n为可选物品个数,γ,β,χ为常数),该并行算法具有最优性能。随后,将带支配技术的动态规划串行算法扩展为并行算法。在负载均衡的情况下,该算法的时间复杂度为O(min(?))。(4)最后,实验验证了各个算法对于求解不同类别的0-1背包问题呈现不同的特点,结论如下：一般动态规划算法和本文提出的RKP算法对背包问题的类别不敏感,也就在求解强相关,弱相关和不相关的背包问题时所耗费的时间差别不大；基于二表思想的混合算法在求解强相关的0-1背包问题时性能较差；令人感到意外的是以Dantzig价值上界作为限界函数的分支限界算法在求解强相关的背包问题时所表现的性能不如回溯法；递归法只适应于小规模问题,并它们在求解强相关的0-1背包问题时性能很差。