求解0-1背包问题的一种新混合算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (4): 50-53.

求解0-1背包问题的一种新混合算法

孙怀影1，耿寅融1，单谦2

1.暨南大学信息科学技术学院计算机科学系，广州 510632
2.暨南大学产业经济研究院产业经济学系，广州 510632

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-01 发布日期:2012-04-05

New hybrid algorithm to solve 0-1 knapsack problem

SUN Huaiying1, GENG Yinrong1, SHAN Qian2

1.Department of Computer Science, College of Information Science and Technology, Jinan University, Guangzhou 510632, China
2.Department of Industrial Economics, Institute of Industrial Economics, Jinan University, Guangzhou 510632, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-01 Published:2012-04-05

摘要/Abstract

摘要： 用动态规划算法求解0-1背包问题的时空复杂度为O（nC）。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发，给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点，设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O（nC）；它消除了回溯阶段，并且为求得放入背包的物品所使用的空间复杂度仅为O（「n/d?+C），其中d为计算机字长。实验结果表明，混合算法的工作效率与理论分析相同。

关键词: 0-1背包问题, 动态规划, 分治策略, 混合算法

Abstract: When using dynamic programming algorithm to solve 0-1 knapsack problem, its time complexity and space complexity both are O（nC）. Its space complexity is not acceptable in case of large scale problem. From the recursive equations for computing optimal value of 0-1 knapsack problem, Memory Efficient Dynamic Programming（MEDP） is proposed. In order to conquer the drawback of MEDP, a new hybrid algorithm is put forward, which combines divided-and-conquered strategy with it and whose time complexity is O（nC）. The hybrid algorithm eliminates the backtracking step, while it can find the goods put into the knapsack under the space complexity O（「n/d? + C）, where d is the word length of computer. Experimental result demonstrates that the algorithm works identically with the theory.

Key words: 0-1 knapsack problem, dynamic programming, divided-and-conquered, hybrid algorithm

孙怀影1，耿寅融1，单谦2. 求解0-1背包问题的一种新混合算法[J]. 计算机工程与应用, 2012, 48(4): 50-53.

SUN Huaiying1, GENG Yinrong1, SHAN Qian2. New hybrid algorithm to solve 0-1 knapsack problem[J]. Computer Engineering and Applications, 2012, 48(4): 50-53.

[1]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[2]	巫光福，陈颖. 花授粉算法研究与应用综述[J]. 计算机工程与应用, 2021, 57(15): 30-41.
[3]	廖列法，杨红. 天牛须搜索算法研究综述[J]. 计算机工程与应用, 2021, 57(12): 54-64.
[4]	周睿慜，李辉. 改进动态规划算法的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(21): 20-24.
[5]	闫旭，叶春明. 混合蝗虫优化算法求解作业车间调度问题[J]. 计算机工程与应用, 2019, 55(6): 257-264.
[6]	陈俊杰，同淑荣，聂亚菲，张静文. 考虑胜任力水平的研发项目群人力资源调度[J]. 计算机工程与应用, 2019, 55(3): 209-218.
[7]	连玮. 采用树表示的全局最优形状匹配算法[J]. 计算机工程与应用, 2019, 55(1): 217-225.
[8]	张雨，崔耀东，梁泽华. 多尺寸圆木二维下料问题研究[J]. 计算机工程与应用, 2018, 54(19): 266-270.
[9]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[10]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[11]	靳雁霞，任超，李照，程思岳，王贺，韩慧妍. 融合智能算法的变形体碰撞检测算法研究[J]. 计算机工程与应用, 2017, 53(19): 130-135.
[12]	孙培双，韩其睿. 彩色图像最优拼接线的改进算法研究[J]. 计算机工程与应用, 2016, 52(21): 218-221.
[13]	方刚1，张社民2. 三元统计语言模型对基因表达载体设计的优化[J]. 计算机工程与应用, 2016, 52(15): 60-64.
[14]	张新功，王慧，柏世坤. 最小化误工工件个数的两代理单机排序问题[J]. 计算机工程与应用, 2016, 52(14): 32-36.
[15]	李惠光，李峰，邵暖，沙晓鹏，王帅. 基于图像分割和控制点的立体匹配算法研究[J]. 计算机工程与应用, 2015, 51(23): 160-163.