背包问题是组合优化学科中一个经典而著名的问题,它的研究价值不言而喻,吸引了众多专家学者从各个角度开展对其的研究工作,各种算法设计思想也应运而生。由于背包问题的NP完全性,如何在算法的时间效率和求解精度上取得有效的平衡,成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能,可以利用它来发现背包问题解的相似的状态空间,然后进行约减,从而克服背包问题的NP困难性。本文研究了背包问题的背景、国内外研究现状和发展趋势,分析了背包问题的性质、各种形式的数学模型和算法设计策略。在完成以上的基础工作后,我们提出自己的理论创新,构建了基于聚类分析的背包问题求解模型,并将其应用于求解0/1背包问题、子集和问题和多维背包问题。在实验部分,我们评估了模型的性能,发现模型具有良好的性能和稳定的近似比,并且在时间效率和求解精度两者之间能够找到一个比较有效的平衡点。本文的创新点如下:(1)在掌握数据挖掘核心技术和理念的基础上,根据对背包问题特性的分析,将经典的背包问题和新兴的数据挖掘技术有机地结合起来,在背包问题节点扩展的过程中引入集中性和多样性策略,提出了一个基于聚类分析的背包问题求解模型;(2)基于聚类分析的背包问题求解模型具有良好的可扩展性,它可以根据不同的求解实例采用适合情况的模块。在减少背包问题解的状态空间的过程中,模型可以实现无监督自动学习,去掉比较相似的状态空间,为状态空间的扩展创造有利的条件;通过二分法的使用,进一步优化了模型的性能;(3)根据基于聚类分析的背包问题求解模型,实现了0/1背包问题、子集和问题和多维背包问题的算法研究。