求解0-1背包问题的动态规划改进算法分析  

Analysis of improved algorithm of dynamic programming solving 0-1 knapsack problem

作　　者：李军民[1] 傅云凤 

机构地区：[1]西安科技大学计算机学院,陕西西安710054

出　　处：《西北大学学报（自然科学版）》2014年第5期729-732,共4页Journal of Northwest University（Natural Science Edition）

基　　金：陕西省教育厅专项科研计划基金资助项目(09JK594)

摘　　要：为了改善动态规划法的空间复杂度,基于动态规划算法的一种改进策略,提出了采用动态链表结构存储数据的实现方式,从而达到降低空间复杂度的目的。通过运算验证,表明该改进方法是可行有效的,且其空间复杂度有所优化。The 0 - 1 knapsack problem is a traditional integer programming problem. Relying on the characteristics of optimal substructure and overlapping sub-problems, there have been many methods to solve it. In this paper, to improve the space complexity of dynamic programming algorithm, based on an improvement strategy of dynamic programming algorithm, an implementation model of the dynamic Linked-list storing data is proposed to achieve the aim of lowering space complexity. Through the simulation computation, the method is proved to be feasible and effective, and the optimization of its space complexity is confirmed.

关 键 词：0-1背包 动态规划 空间复杂度 动态链表 改进算法 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]