摘要
经典算法一般采用迭代过程求解连续凸二次背包问题,研究了求解可分离连续凸二次背包问题的直接算法。分析了可分离连续凸二次背包问题的结构特性,通过两个命题和两个定理研究了可分离连续凸二次背包问题的解的特性,提出了一种快速的求解该问题的直接算法。该算法能快速有效地求解可分离连续凸二次背包问题的最优解,算法的时间复杂度和空间复杂度都是O(n),都比经典算法节约很多。
Classical algorithms often solve continuous convex quadratic knapsack problem through iteration process, a direct algorithm is investigated for separable continuous convex quadratic knapsack problem. By analyzing the structural characteristics of the problem, and investigating the properties of the solutions by giving two propositions and two theorems, a direct algorithm for separable continuous convex quadratic knapsack problem is proposed, by which the optimal solution to the problem can be obtained fast and effectively. The computational complexity on time and space of the proposed algorithm are both O (n), which are both smaller than those of the classical algorithms.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2005年第2期331-334,共4页
Systems Engineering and Electronics
基金
国家自然科学基金(70172041)
安徽省自然科学基金(03042308)资助课题
关键词
凸二次背包问题
可分离问题
松弛
算法
convex quadratic knapsack problem
separable problem
relaxation
algorithm
