Research and Application on Method of Solving Knapsack Problem based on Clustering Analysis

摘要

背包问题是组合优化学科中一个经典而著名的问题，它的研究价值不言而喻，吸引了众多专家学者从各个角度开展对其的研究工作，各种算法设计思想也应运而生。由于背包问题的NP完全性，如何在算法的时间效率和求解精度上取得有效的平衡，成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能，可以利用它来发现背包问题解的相似的状态空间，然后进行约减，从而克服背包问题的NP困难性。 本文研究了背包问题的背景、国内外研究现状和发展趋势，分析了背包问题的性质、各种形式的数学模型和算法设计策略。在完成以上的基础工作后，我们提出自己的理论创新，构建了基于聚...