背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。从计算复杂性理论看,背包问题是一个经典NP难解问题。半个多世纪以来,该问题一直是算法与复杂性研究的热点问题之一。论文研究了背包问题的实用求解算法,提出了改进的新算法,并利用Maltab对几种算法进行了仿真实验,测试的结果显示出新算法在解决0/1背包问题时表现出了良好的性能。在论文中主要进行的工作如下:1. 首先讨论了传统算法设计技术求解背包问题的方法,主要有递归算法、动态规划算法、分支定界法、图论法、贪婪算法等,同时讨论了背包问题在电子商务公钥密码系统中的应用。2. 论文中重点研究了遗传算法(GA)在解决背包问题上的应用,在广泛了解现有遗传算法的优缺点的基础上,结合耗散结构理论提出了耗散遗传算法(DGA)。耗散遗传算法能够在一定程度上克服普通遗传算法的缺点。通过仿真实验证实了该方法在解决0/1背包问题上的有效性。3. 另外本文还研究了蚁群算法(ACO)在解决背包问题上的应用,蚁群优化算法是新出现的一种模拟蚂蚁觅食行为的仿生随机优化算法,在货郎商问题(TSP)等优化问题上有较为成熟的应用,本文将其应用在背包问题中,也取得了较好的效果。4. 同时本文也研究了粒子群算法(PSO)在解决背包问题上的应用。粒子群优化算法是在对模拟鸟群捕食行为的研究中产生的一种新算法,本文将其与其他算法进行了对比,并给出了在0/1背包问题上的解决方法。