基于核的MMKP问题算法研究

• 作者: 郑晓月
• 来源期刊: 电子设计工程
• 学科: 工学
• 关键词: 核 多维多选择背包问题 B＆B算法 分支定界 解空间
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 计算机技术与应用
• 页码范围: 1-4
• 页数: 4页
• 分类号: TP301.6
• 字数: 5224字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-6236.2012.11.001

摘要

多维多选择背包问题（MMKP）是0-1背包问题的延伸，背包核已经被用来设计解决背包问题的高效算法。目的是研究如何获得一种背包核，并以此高效处理多维多选择背包问题。首先给出了一种方法确定MMKP的核．然后阐述了利用核精确解决MMKP问题的B＆B算法，列出了具体的算法步骤。在分析了算法的存储复杂度后，将算法在各种实例上的运行效果与目前解决MMKP问题的常用算法的运行效果进行了比较，发现本文的算法性能优于以往任何算法。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑晓月	商丘师范学院计算机与信息技术学院	18	18	3.0	3.0