| 多选择背包问题的快速求解算法 |
| |
| 引用本文： | 鲍江宏,杨启贵.多选择背包问题的快速求解算法[J].华南理工大学学报(自然科学版),2009,37(4). |
| |
| 作者姓名： | 鲍江宏 杨启贵 |
| |
| 作者单位： | 华南理工大学,数学系,广东,广州,510640 |
| |
| 摘 要： | 背包问题属于组合优化中的经典问题,它有许多重要的变形,其中以多选择背包问题最为复杂.为更快地求解多选择背包问题,文中首先对该问题进行了理论分析,然后基于动态规划提出了一种新的求解算法,并对一个复杂的案例进行了测试.结果表明,这种新算法比遗传算法快9.4倍,比传统的0-1整数规划求解法快78倍.通过对数学模型的改进可大大降低问题的规模.更重要的是,所用方法可避免求解任何线性规划问题.
|
| 关 键 词： | 背包问题 组合优化 动态规划 |
Fast Solution Algorithm of Multiple-Choice Knapsack Problem |
| |
| Bao Jiang-hong,Yang Qi-gui.Fast Solution Algorithm of Multiple-Choice Knapsack Problem[J].Journal of South China University of Technology(Natural Science Edition),2009,37(4). |
| |
| Authors: | Bao Jiang-hong Yang Qi-gui |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
