整数背包问题的应用及其算法研究  

STUDY ON THE APPLICATION OF INTEGER KNAPSACK PROBLEM AND ITS ALGORITHM

作　　者：任瑞征[1] 严蔚敏[2] 

机构地区：[1]山西大学计算机科学系,太原030006 [2]清华大学计算机科学与技术系,北京100084

出　　处：《小型微型计算机系统》2001年第2期204-206,共3页Journal of Chinese Computer Systems

基　　金：山西省教委教学研究项目!的支持(课题编号 :0 82 40 6 A)

摘　　要：本文应用整数背包问题有关理论 ,对 CD曲目智能编辑转录和条型钢材优化切割等应用问题进行了讨论 ,提出了一个解决此类问题的数学模型 .之后 ,分别给出了求其最优解和近似解的算法 ,并提供了该数学模型及算法的应用建议 .This paper first discusses the problems of intelligently editing and recording CD tracks and optimally cutting bar steel by using the related theory of integer knapsack problem. A mathematical model solving such kind of problems are put forward. Then, the paper respectively presents the algorithms that can get optimal and approximate solution. Some proposals for the application of this mathematical model and algorithms are given.

关 键 词：整数背包问题 最优解 近似算法 组合优化 数学模型 

分 类 号：O224[理学—运筹学与控制论]