郝 翔，李香军

(河北地质大学 信息工程学院，河北 石家庄 050031)

0 引言

0-1背包问题（0-1 Knapsack problem, 0-1KP）[1-2]既是一个 NP-complete问题，也是一个典型的组合优化问题，在资源分配、项目组合和整数规划等[3]领域有广泛的应用。0-1KP衍化出了多种扩展形式，其中具有单连续变量的背包问题（knapsack problem with a single continuous variable, KPC）[4]是一个在物品生产、组织协调、分配管理以及其他经济问题中具有重要的应用价值的0-1KP问题扩展形式之一，由 Marchand和 Wolsey于 1999年提出。KPC问题带有一个连续变量S，S的连续变化会导致背包容量发生扩大或者缩小，从而导致问题求解难度增大。由于0-1KP是KPC的一个特例，因此KPC也是一个NP-complete问题，如何对其进行快速、高效求解是一个重要的问题。

2011年，Lin等人[5]给出了KPC问题的混合整型规划公式，并通过将KPC问题转化为0-1KP和 pseudo-KP的方法，分别利用动态规划算法COMBO和分支定界算法EXPKNAP进行求解，显然算法具有很高的时间复杂度。2012年，Buther和Briskorn[6]提出了等价构造法和启发式策略，将KPC转化为0-1KP问题，最后通过COMBO方法对转化后的KP问题进行求解，执行速度仍较慢。2018年，He等人[7]首先利用放缩法将KPC中的连续变量离散化，并基于动态规划法提出了求解KPC的精确算法DP-KPC。上述算法均采用了动态规划等精确算法，时间复杂度都较高，在求解大规模KPC实例时存在速度慢、在限定时间内不能获得精确解的缺点，不能满足实际应用中时效性要求。为此，He等人[8]于 2018年提出了基于演化算法求解KPC问题的新思路，在利用降维法消除连续变量的基础上，基于离散差分演化算法给出了求解KPC的算法S-HBDE和B-HBDE，求解效果有了很大的提高。……