无限制背包问题的爬山算法  

Hill Climbing Algorithm for Unconstraint Knapsack Problem

作　　者：宋翔[1] 聂义勇[1] 储诚斌 

机构地区：[1]中国科学院沈阳自动化研究所 [2]特鲁瓦科技大学,法国特鲁瓦10009

出　　处：《小型微型计算机系统》2004年第7期1352-1355,共4页Journal of Chinese Computer Systems

摘　　要：给出了一种求解整数背包问题的爬山解法 ,并对该算法的计算复杂度及最坏情形进行了理论分析 .通过与经典的求解背包问题方法的对比研究 ,给出了该算法的适用范围并展示其优越性 .数值实验表明 ,该算法简便易行 ,在其适用范围内具有计算复杂度低 ,近优程度高等优点 .A new hill climbing algorithm for the unconstraint knapsack problem was presented. The complexity and the worst case condition of this new algorithm were analyzed. By the comparison with some classical algorithms, the application scope is given and the superiority is displayed about this algorithm. It has been shown in numerical experiments that the new algorithm is easy to implement and has the virtue of low computational complexity and high approximate optimization degree within its applicable scope.

关 键 词：背包问题 无限制 爬山算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]