| 0/1背包问题快速降价法及其应用 |
| |
| 引用本文： | 宁爱兵,马良.0/1背包问题快速降价法及其应用[J].系统管理学报,2005,14(4):372-375. |
| |
| 作者姓名： | 宁爱兵 马良 |
| |
| 作者单位： | 上海理工大学,管理学院,上海,200093 |
| |
| 基金项目： | 国家自然科学基金资助项目(70471065)，上海市教委重点学科建设资助项目 |
| |
| 摘 要： | 用数学方法分析了0/1背包问题的特性,提出了一个快速降价算法,该算法能成批确定一定在最优解中的物品和成批排除一定不在最优解中的物品。该算法既可单独使用,又可与启发式算法结合达到更好的结果。文中给出了应用实例及其分析。
|
| 关 键 词： | 0/1背包问题 快速降阶算法 上界 下界 |
| 文章编号： | 1005-2542(2005)04-0372-04 |
| 修稿时间： | 2004年3月24日 |
A Quick Reduction Algorithm and Its Applications for 0/1-Knapsack Problem |
| |
| NING Ai-bing,MA Liang.A Quick Reduction Algorithm and Its Applications for 0/1-Knapsack Problem[J].Systems Engineering Theory·Methodology·Applications,2005,14(4):372-375. |
| |
| Authors: | NING Ai-bing MA Liang |
| |
| Abstract: | Based on mathematical inference, this paper proposes a quick reduction algorithm for 0/1-knapsack problem. The algorithm can make certain which items would be in the best soltuion in batches and which items would not be. The algorithm not only can be used singly, but also can be combined with other heuristic algorithms to get better solutions. Series of examples and instances are solved and analysed. |
| |
| Keywords: | 0/1-knapsack problem quick reduction algorithm upper bound lower bound |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
