摘要
在动态规划算法的基础上提出了改进算法,对于0-1背包问题,改进了动态规划算法的状态表示以减少需要计算的状态个数来求解该问题;对于完全背包问题,简化了动态规划算法状态的决策依赖关系来求解该问题.实验结果表明:所提出的改进算法在时空效率上具有一定的有效性和优越性.
In this paper, we proposed improved algorithms based on dynamic programming thinking. For the 0-1 knapsack problem, we improved the status representation of dynamic programming algorithm to reduce the number of states needed to calculate. For the complete knapsack problem, we simplified the decision dependency status of dynamic programming algorithm to solve the problem. Experimental results showed that the improved algorithms have some validity and superiority in space and time efficiency.
出处
《中南民族大学学报（自然科学版）》
CAS
北大核心
2016年第4期101-105,共5页
Journal of South-Central University for Nationalities：Natural Science Edition
基金
国家自然科学基金资助项目(71003038)
关键词
背包问题
动态规划
状态表示
决策依赖
knapsack problem
dynamic programming
state representation
decision dependency
