基于核算法解决多维多选择背包问题

• 作者: 康鲲鹏
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 多维多选择背包问题 核 分支定界 整数线性规划 组合优化
• 年，卷（期）: 2012,（8）
• 所属期刊栏目: 先进计算
• 页码范围: 2168-2171,2175
• 分类号: TP18
• 字数: 6002字
• 语种: 中文
• DOI: 10.3724/SP.J.1087.2012.02168

摘要

针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核.首先论述了如何在一般背包问题中获得核；接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并利用三种备选方案得出MMKP的核,亦即子空间.第一种方案是基于观察数据E[lc]和E[d∞]比较小来得到核；第二种方案基于基本解和最优解的曼哈顿距离不算太远来实施；第三种方案是为所有元素定义一个全序并取第一组k元素作为核.比较了这三种方案的不同与优劣,结果表明:第一种方案比其他两种方案无论从定义子空间的精度和枚举时间平均值上,性能都更优越,利用该方案定义的核能高效解决MMKP.

作者信息

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