| 求解复杂背包问题的一种贪婪算法 |
| |
| 引用本文： | 贾欣鑫,罗亮,郭丽峰,何尚录. 求解复杂背包问题的一种贪婪算法[J]. 重庆理工大学学报(自然科学版), 2008, 22(9) |
| |
| 作者姓名： | 贾欣鑫 罗亮 郭丽峰 何尚录 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院 |
| |
| 摘 要： | 给出了求解背包问题的一种贪婪算法,引用了模函数对算法进行了讨论,从理论上证明了这一算法的性能保证,最后用此算法求解了一个背包问题.
|
| 关 键 词： | 组合优化 模集函数 贪婪算法 背包问题 |
A Greedy Algorithm for Knapsack Problem |
| |
| JIA Xin-xin,LUO Liang,GUO Li-feng,HE Shang-lu. A Greedy Algorithm for Knapsack Problem[J]. Journal of Chongqing University of Technology(Natural Science), 2008, 22(9) |
| |
| Authors: | JIA Xin-xin LUO Liang GUO Li-feng HE Shang-lu |
| |
| Abstract: | This paper presents a greedy algorithm for knapsack problem,discusses it with supermodular set function,and proves the performance guarantee of the algorithm.In the end,this paper uses this algorithm to solve a knapsack problem. |
| |
| Keywords: | combinatorial optimization set function greedy algorithm knapsack problem |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
