| 基于核的MMKP问题算法研究 |
| |
| 引用本文： | 郑晓月.基于核的MMKP问题算法研究[J].电子设计工程,2012,20(11):1-4. |
| |
| 作者姓名： | 郑晓月 |
| |
| 作者单位： | 商丘师范学院计算机与信息技术学院,河南商丘,476000 |
| |
| 基金项目： | 河南省科技厅基础与前沿技术研究项目 |
| |
| 摘 要： | 多维多选择背包问题（MMKP）是0-1背包问题的延伸，背包核已经被用来设计解决背包问题的高效算法。目的是研究如何获得一种背包核，并以此高效处理多维多选择背包问题。首先给出了一种方法确定MMKP的核．然后阐述了利用核精确解决MMKP问题的B＆B算法，列出了具体的算法步骤。在分析了算法的存储复杂度后，将算法在各种实例上的运行效果与目前解决MMKP问题的常用算法的运行效果进行了比较，发现本文的算法性能优于以往任何算法。
|
| 关 键 词： | 核 多维多选择背包问题 B＆B算法 分支定界 解空间 |
Algorithm research of the multidimensional multiple-choice knapsack problem based on core |
| |
| ZHENG Xiao-yue.Algorithm research of the multidimensional multiple-choice knapsack problem based on core[J].Electronic Design Engineering,2012,20(11):1-4. |
| |
| Authors: | ZHENG Xiao-yue |
| |
| Affiliation: | ZHENG Xiao-yue(School of Computer and Information Technology,Shangqiu Normal University,Shangqiu 476000,China) |
| |
| Abstract: | The multidimensional multiple-choice knapsack problem(MMKP) is an extension of the 0-1 knapsack problem.The core concept has been used to design efficient algorithms for the knapsack problem.The purpose of the research is how to obtain a core and use it to solve the MMKP effectively.Firstly,the B&B algorithm that solves MMKP exactly is presented,and simultaneously,concrete steps are list to explain our algorithm.After the analysis of memory complexity,we compared the algorithm presented in the paper against the specific algorithm for MMKP so far,it completely outperform the previous algorithm. |
| |
| Keywords: | core MMKP B&B algorithm branch-and-bound solution space |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
