论文部分内容阅读
收缩背包问题(collapsing knapsack problem,CKP)是0-1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需要,在对CKP问题分解的基础上,给出了求解每个子问题的分枝界限算法;提出了基于MIMD-DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响.