【作者】 刘裴寰； 姜青山； 王备战； 史亮；

【机构】 厦门大学软件学院；

【摘要】 <正>1前言Cornuejols和Dawande在文[1]中提出了著名的市场共享问题的可行性问题,这就是通常的多维背包问题（Multidimensional knapsack problem,MKP）。该问题的具体描述如下:给定一个n×m矩阵A和一个m维列向量b,要求判断是否存在一个n维的二值向量X={x₁,x₂,…,x_n},使得式（1）成立。更多还原

【Abstract】 The multidimensional knapsack problem(MKP) is a classical combined optimization problem,it plays a very important role in information security,mathematics and practical project application field,so much effort has been done in order to find practical algorithm for solving the multidimensional knapsack problem.Our paper applies the method of data mining to solve classical problem.Based on the clustering method,this paper proposes an approximate algorithm based on k-means clustering for solving the multidimensional knapsack problem.The stochastic and comparative experiments show that our proposed algorithm for solving the multidimensional knapsack problem has efficient time measurement and steady approximate factor.更多还原