动态规划求解0-1背包问题的教学探索  

Teaching Exploration in Dynamic Programming for Solving the 0-1 Knapsack Problem

作　　者：李志洁[1] 郑海旭[1] 

机构地区：[1]大连民族学院计算机科学与工程学院,辽宁大连116605

出　　处：《大连民族学院学报》2010年第1期80-84,共5页Journal of Dalian Nationalities University

基　　金：大连民族学院博士启动基金(20086205)

摘　　要：针对动态规划在0-1背包问题中求解最优值时的教学难度,结合教学过程和特点,对计算最优值的算法进行了改进,在与最优值递归公式保持一致的情况下简化了迭代过程,消除算法技巧,增加了算法的规范性和连贯性,收到了理想的教学效果。Given all the difficulties in teaching about using dynamic programming to find the optimal value for the 0 - 1 knapsack problem, we improved the algorithm for optimal value calculation in combination with the process and characteristics of teaching. With the consistence with the recursive formula for the optimal value maintained, we simplified the iterative process and removed algorithm skills, thereby increasing the compliance and the coherence of the algorithm and hence receiving better teaching results.

关 键 词：算法 动态规划 0—1背包问题 

分 类 号：G642.0[文化科学—高等教育学]