Cornuejols和Dawande在文中提出了著名的市场共享问题的可行性问题,这就是通常的多维背包问题(Multidimensional knapsack problem,MKP).该问题的具体描述如下:给定一个n×m矩阵A和一个m维列向量b,要求判断是否存在一个n维的二值向量X={x1,x2,…,xn},使得式(1)成立. n∑j=1aijxj=bi,i=1,2,…,m 数学上已经证明:多维背包问题有解的充要条件是一维背包问题有解.众所周知,一维的0/1背包问题是NP完全问题.相比较而言,多维的0/1背包问题的复杂度更高.由于求解的指数时间复杂性,背包问题在信息安全领域和数论研究中有着很重要的应用.另外还有许多实际工程的优化问题都可以归结建模为背包问题,典型的有:集装箱装载问题、批量切割问题、项目选择决策问题等.正因为有着如此广泛的应用,通过各种有效的算法设计策略来降低求解背包问题过于庞大的计算量,寻找可行的算法,具有重要的理论意义和实践意义. 数据挖掘是一个新兴的学科,近年来数据挖掘技术已经深入到各个知识领域.怎样更好地将数据挖掘技术与背景知识的学习结合起来正在成为一个新的研究热点.本文应用了这样的思想,尝试了结合聚类分析的方法求解多维背包问题,提出的算法对于求解经典的多维背包问题具有高效的时间效率和稳定的近似比,可以在实际的工程应用领域中得到有价值的应用。