可分离的二次背包问题的一种直接算法

上海大学学报(自然科学版) ›› 2010, Vol. 16 ›› Issue (4): 387-393.

可分离的二次背包问题的一种直接算法

任燕,陈伟

（上海大学理学院，上海 200444）

收稿日期:2009-05-13 出版日期:2010-08-30 发布日期:2010-08-30
通讯作者: 陈伟(1965～)，女，副教授，研究方向为整数规划. E-mail:chenwei@staff.shu.edu.cn

Algorithm for Direct Solution of Separable Quadratic Knapsack Problem

REN Yan,CHEN Wei

(College of Sciences, Shanghai University, Shanghai 200444, China)

Received:2009-05-13 Online:2010-08-30 Published:2010-08-30

摘要/Abstract

摘要：

二次背包问题是一个NP hard问题.给出一般的可分离二次背包问题的一种快速求解的直接算法,分析可分离连续二次背包问题的结构特性,并研究此问题最优解与拉格朗日系数λ的关系.在此基础上,提出通过调节λ来找到可分离二次背包问题的局部最优解的算法,此算法的计算复杂度为O(n).

关键词: 二次背包问题;Karush-Kuhn-Tucker(KKT)条件;可分离;拉格朗日系数

Abstract:

Quadratic knapsack problem is NP hard. This paper presents an algorithm to directly obtain a local optimal solution of a separable quadratic knapsack problem. By analyzing the structural characteristics of the problem, we study the relations between Lagrangian λ and the optimal solution. An algorithm is presented in which the Lagrangian λ is adjusted to give a local optimal solution. Computational complexity is O(n). 

Key words: quadratic knapsack problem; KarushKuhnTucker (KKT) condition; separable; Lagrangian

中图分类号:

O 211.4

任燕,陈伟. 可分离的二次背包问题的一种直接算法[J]. 上海大学学报(自然科学版), 2010, 16(4): 387-393.

REN Yan,CHEN Wei. Algorithm for Direct Solution of Separable Quadratic Knapsack Problem[J]. Journal of Shanghai University（Natural Science Edition）, 2010, 16(4): 387-393.

[1]	张茜1,2, 金翊1,2,3, 宋凯1,2, 高桓1,2. 三值光学计算机MPI编程技术在超算集群中的使用[J]. 上海大学学报(自然科学版), 2014, 20(2): 180-189.
[2]	秦世伟, 莫泷, 周艳坤. 静压桩沉桩及已打入桩遮拦效应的数值模拟[J]. 上海大学学报(自然科学版), 2014, 20(2): 239-249.
[3]	徐秦乐1, 张金艺1,2,3, 徐惠政1, 李若涵2, 张晶晶2. 高精度故障电弧检测多传感器数据融合算法[J]. 上海大学学报(自然科学版), 2014, 20(2): 165-173.
[4]	黄青华, 李琳, 赖士村. 基于 RBF 神经网络的头相关传输函数的个性化建模方法[J]. 上海大学学报(自然科学版), 2014, 20(2): 157-164.
[5]	曹绍梅, 张大卫, 冯欣, 迟涛, 施利毅. 尖晶石结构Li₄Ti₅O₁₂的制备及其电化学性能[J]. 上海大学学报(自然科学版), 2012, 18(6): 572-576.
[6]	张翔, 郝雷, 王卿文. 矩阵方程组中心对称解的极秩[J]. 上海大学学报(自然科学版), 2012, 18(6): 596-600.
[7]	李东兵，李国平，滕国伟，赵海武，王国中,李萍. 一种新的自适应维纳滤波方法[J]. 上海大学学报(自然科学版), 2012, 18(6): 555-560.
[8]	钱佳民，徐闰，汤敏燕. 小尺度薄型封装焊点失效机理和可靠性设计[J]. 上海大学学报(自然科学版), 2012, 18(6): 561-566.
[9]	刘婧颖, 谢耀平, 陈业新, 黄晓君, 赵世金. H和B原子在有序态 Ni₃Fe 表面的吸附[J]. 上海大学学报(自然科学版), 2012, 18(6): 567-571.
[10]	崔泽, 韩增军. 基于自运动的仿人七自由度机械臂逆解算法[J]. 上海大学学报(自然科学版), 2012, 18(6): 589-605.
[11]	郭路军. p-余弦变换及其在凸几何分析中的应用[J]. 上海大学学报(自然科学版), 2012, 18(6): 601-605.
[12]	江金胜, 董力耘. 信号灯交叉口处综合待行区的建模与模拟[J]. 上海大学学报(自然科学版), 2012, 18(6): 606-611.
[13]	蔡茂源，张田忠. 多壁碳纳米管压缩与弯曲时屈曲的ANSYS模拟[J]. 上海大学学报(自然科学版), 2012, 18(6): 612-616.
[14]	时伉丽, 丁虎, 陈立群, 储德林. 移动载荷黏弹性Pasternak地基梁动力学响应[J]. 上海大学学报(自然科学版), 2012, 18(6): 617-621.
[15]	沈佳铖，任九生. 动脉壁的动力响应特性[J]. 上海大学学报(自然科学版), 2012, 18(6): 622-626.