摘要
对于0-1背包这一NP问题,目前仍没有最优算法解决。文中给出了利用穷举法、动态规划法、回溯法及分支限界法等几类方法来解决此问题,并分别编写程序进行试验。运行多组数据,得到这四种算法在时间复杂度上的差异,通过这种方法引导学生将理论应用起来,提升学生的动手能力,达到更好的教学效果。同时,也进一步加深了学生对不同算法策略的理解并灵活运用。
For the NP problem of 0-1 backpack,there is still no optimal algorithm to solve it..In this paper, several methods such as exhaustive method,dynamic programming method,backtracking method and branch and bound method are used to solve this problem,and the program is written to test.Run multiple sets of data to get the difference in time complexity of these four algorithms.This method guides students to apply the theory to improve students practical ability and achieve better teaching results.At the same time,it has further deepened students understanding of different algorithm strategies and applied them flexibly.
作者
乔丽娟
徐岩
Qiao Li-juan;Xu Yan(College of software,Qufu Normal University,Qufu 273165,China;Network Information Center,Qufu Normal University,Qufu 273165,China)
出处
《电子技术（上海）》
2018年第11期15-17,共3页
Electronic Technology
基金
曲阜师范大学2017年校级实验技术研究项目(SJ201714)
关键词
0-1背包
穷举法
动态规划
回溯法
分支限界法
时间复杂度
0-1 knapsack problem
exhaustive method
dynamic programming
backtracking method
branch and bound methods
time complexity
