The cone has been used to design efficient algorithms for the knapsack problem. Several methods were put forward to obtain a core for Multidimensional Mutiple-choice Knapsack Problem (MMKP) as there is no algorithm based on core now. The method of obtaining a core of the Knapsack Problem (KP) was discussed firstly, and then the base solution and ordering relations of MMKP were explained in detail according to the metrics set beforehand. After that, the core which can be called subspace was obtained by three methods. The firrst method was based on the observation that which of E[ lc ] and E[ d00 ] was smaller. The second method was based on the observation that the Manhattan distance of the base solution was not too far from the optimal solution. In the third method, a total ordering was defined among all items and the first k items were taken as the core. The comparative study shows that the performance of the first one is superior on both accuracy and enumeration time. The MMKP can be solved efficiently with this method.%针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核.首先论述了如何在一般背包问题中获得核；接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并利用三种备选方案得出MMKP的核,亦即子空间.第一种方案是基于观察数据E[lc]和E[d∞]比较小来得到核；第二种方案基于基本解和最优解的曼哈顿距离不算太远来实施；第三种方案是为所有元素定义一个全序并取第一组k元素作为核.比较了这三种方案的不同与优劣,结果表明:第一种方案比其他两种方案无论从定义子空间的精度和枚举时间平均值上,性能都更优越,利用该方案定义的核能高效解决MMKP.
展开▼
