|
|||||
|
|
| 背包问题的一种自适应算法 | |
| 引用本文： | 李肯立,李庆华,戴光明,周炎涛.背包问题的一种自适应算法[J].计算机研究与发展,2004,41(7):1292-1297. |
| 作者姓名： | 李肯立 李庆华 戴光明 周炎涛 |
| 作者单位： | 1. 华中科技大学计算机科学与技术学院,武汉,430074;湖南大学计算机科学与通讯学院,长沙,410082 2. 华中科技大学计算机科学与技术学院,武汉,430074 3. 湖南大学计算机科学与通讯学院,长沙,410082 |
| 基金项目： | 国家自然科学基金项目 ( 60 2 73 0 75 )，国家“八六三”高技术研究发展计划基金项目 ( 863 3 0 6ZD 11 0 1 0 6) |
| 摘 要： | 背包问题是经典的NP-hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4)，在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能． |
| 关 键 词： | 背包问题 NP-hard 自适应算法 密钥系统 |
An Adaptive Algorithm for the Knapsack Problem |
|
| LI Ken-Li ,LI Qing-Hua ,DAI Guang-Ming ,and ZHOU Yan-Tao.An Adaptive Algorithm for the Knapsack Problem[J].Journal of Computer Research and Development,2004,41(7):1292-1297. | |
| Authors: | LI Ken-Li LI Qing-Hua DAI Guang-Ming and ZHOU Yan-Tao |
| Affiliation: | LI Ken-Li 1,2,LI Qing-Hua 1,DAI Guang-Ming 1,and ZHOU Yan-Tao 2 1 |
| Abstract: | |
| Keywords: | knapsack problem NP-hard adaptive algorithm cryptosystem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |