摘要
给出了求解背包问题的一种贪婪算法,引用了模函数对算法进行了讨论,从理论上证明了这一算法的性能保证,最后用此算法求解了一个背包问题.
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.
出处
《重庆工学院学报（自然科学版）》
2008年第9期71-74,共4页
Journal of Chongqing Institute of Technology
基金
兰州交通大学"青蓝"工程资助项目(QL-03-19A)
关键词
组合优化
模集函数
贪婪算法
背包问题
combinatorial optimization
set function
greedy algorithm
knapsack problem
