作　　者： ; ;

机构地区： 上海大学理学院

出　　处： 《上海大学学报（自然科学版）》 2010年第4期387-393,共7页

摘　　要： 二次背包问题是一个NP-hard问题.给出一般的可分离二次背包问题的一种快速求解的直接算法,分析可分离连续二次背包问题的结构特性,并研究此问题最优解与拉格朗日系数λ的关系.在此基础上,提出通过调节λ来找到可分离二次背包问题的局部最优解的算法,此算法的计算复杂度为O(n). Quadratic knapsack problem is NP-hard. local optimal solution of a separable quadratic This paper presents an algorithm to directly obtain a knapsack problem. By analyzing the structural characteristics of the problem, we study the relations between Lagrangian A and the optimal solution. An algorithm is presented in which the Lagrangian A is adjusted to give a local optimal solution. Computational complexity is O（n）.

关 键 词： 二次背包问题 条件 可分离 拉格朗日系数

领　　域： [理学] [理学]