-
题名0-1背包问题上界的快速计算方法
被引量：1
- 1
-
-
作者
王正元
-
机构
火箭军工程大学
-
出处
《火箭军工程大学学报》
2025年第1期31-40,共10页
-
文摘
为提高0-1背包问题上界求解的速度与精确度,分析了拉格朗日松弛方法构造的精确0-1背包问题上界模型,建立了该模型的快速求解算法,证明了精确0-1背包问题上界是拉格朗日乘子的凸函数。由此,提出了精确0-1背包问题最小上界的求解方法,证明了精确0-1背包问题上界是物品数的单峰函数,且0-1背包问题的上界恰好等于物品数为关键物品数(关键物品数-1)时精确0-1背包问题最小上界的最大值。结果表明:该计算方法所需计算量与背包问题物品数成比例,计算速度较快,上界相对较小。通过6500例不同上界计算实验对比,提出的上界计算所需时间约为其他较优算法的15.1%;上界占优比例94.29%,而其他较优算法占优比例仅68.71%。进一步表明该上界算法可以快速构造较好的近似解,从而降低0-1背包问题的维数。
-
关键词
组合优化问题
0-1背包问题
上界
精确0-1背包问题
拉格朗日松弛
-
Keywords
combinatorial optimization problem
0-1 knapsack problem,upper bound
exact k knapsack problem
Lagrangian relaxation
-
分类号
TJ410
[兵器科学与技术—火炮、自动武器与弹药工程]
-
