摘要
在分析多维背包问题和多选择背包问题的基础上,提出一种广义的多维多选择背包问题,给出了该问题的数学模型并改进传统的贪婪算法对其进行了求解。该算法以价值密度为准则,并对每个约束条件先后执行贪婪优化,从而得到问题的近似最优解。
Based on the analysis of the multidimensional knapsack problem and the multiple - choice knapsack problem, the Generalized Muhidimensional Multiplechoice Knapsack Problem （GMMKP） and its mathematical model and improved greedy algorithm for the solution are proposed. The algorithm is based on the value density criteria and has executed the greedy search from one constraint to another constraint, hence we obtain the approximate optimal solution.
出处
《贵州师范学院学报》
2010年第9期17-19,共3页
Journal of Guizhou Education University
关键词
背包问题
贪婪算法
多维多选择背包
Knapsack Problem
greedy algorithm
multidimensional knapsack problem
