0-1背包问题的深度优先算法  

作　　者：胡迎松[1] 

机构地区：[1]华中理工大学计算机科学与工程系

出　　处：《计算机应用研究》1999年第3期32-33,共2页Application Research of Computers

摘　　要：本文介绍了０－１背包问题的一种深度优先（ＤＦＳ）算法，并用概率分析方法给出了算法的时间复杂度和空间复杂度，一般情况下，其时间复杂度在Ｏ（ｎ）到Ｏ（１．５）之间。工程管理上的一类整数规划问题都可归结为０．１背包问题。

关 键 词：整数规划 0-1背包问题 深度优先算法 工程管理 

分 类 号：O221[理学—运筹学与控制论] TU71[理学—数学]