基于核的MMKP问题算法研究  

Algorithm research of the multidimensional multiple-choice knapsack problem based on core

作　　者：郑晓月[1] 

机构地区：[1]商丘师范学院计算机与信息技术学院,河南商丘476000

出　　处：《电子设计工程》2012年第11期1-4,共4页Electronic Design Engineering

基　　金：河南省科技厅基础与前沿技术研究项目(112300410306)

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

关 键 词：核 多维多选择背包问题 B&B算法 分支定界 解空间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]