0-1背包问题上界的快速计算方法  

Fast Algorithm for the Upper Bound of the 0-1 Knapsack Problem

作　　者：王正元 WANG Zhengyuan(Rocket Force University of Engineering,Xi’an 710025,China)

机构地区：[1]火箭军工程大学,陕西西安710025

出　　处：《火箭军工程大学学报》2025年第1期31-40,共10页Journal of Rocket Force University of Engineering

摘　　要：为提高0-1背包问题上界求解的速度与精确度,分析了拉格朗日松弛方法构造的精确0-1背包问题上界模型,建立了该模型的快速求解算法,证明了精确0-1背包问题上界是拉格朗日乘子的凸函数。由此,提出了精确0-1背包问题最小上界的求解方法,证明了精确0-1背包问题上界是物品数的单峰函数,且0-1背包问题的上界恰好等于物品数为关键物品数(关键物品数-1)时精确0-1背包问题最小上界的最大值。结果表明:该计算方法所需计算量与背包问题物品数成比例,计算速度较快,上界相对较小。通过6500例不同上界计算实验对比,提出的上界计算所需时间约为其他较优算法的15.1%;上界占优比例94.29%,而其他较优算法占优比例仅68.71%。进一步表明该上界算法可以快速构造较好的近似解,从而降低0-1背包问题的维数。To improve the computational speed and accuracy of the algorithm for the upper bound of the 0-1 knapsack problem(KP01),this study analyzed the upper bound model of the exact k knapsack problem(E-kKP)constructed by Lagrangian relaxation.First,the upper bound of the(E-kKP)was proven to be a convex function of the Lagrangian multiplier,and an algorithm for the minimum upper bound of(E-kKP)was proposed.Second,the upper bound of the(E-kKP)was determined to be a unimodal function of the number of the items,and the upper bound of the(E-kKP)equaled the maximum value of the minimum upper bound of the(E-kKP)when the number of the items was the key item number(key item number-1).The experiments showed that the algorithm for the upper bound of the(E-kKP)proposed in this study requires a proportional calculation to the number of the items,with fast calculatingion speed and relatively small upper bound.From 6500 experiments with different upper bounds,the calculatingion time of the upper bound in this study is approximately 15.1% of that of other superior algorithms,with an advantage rate of 94.29%,the others have an advantage rate of only 68.71%.In addition,the proposed upper bound algorithm can quickly construct better approximate solutions and reduce the dimensionality of KP01.

关 键 词：组合优化问题 0-1背包问题 上界 精确0-1背包问题 拉格朗日松弛 

分 类 号：TJ410[兵器科学与技术—火炮、自动武器与弹药工程]