动态规划求解0_1背包问题的教学探索.pdfVIP

第 12 卷 　第 1期 大 连 民 族 学 院 学 报 Vo l. 12 ,No. 1 2010年 1月 Jou rna l of D alian N ationa litie s U n iversity January 20 10 文章编号 : 1009 - 3 15X (20 10) 01 - 0080 - 05 动态规划求解 0 - 1背包问题的教学探索 李志洁 ,郑海旭 (大连民族学院 计算机科学与工程学院 ,辽宁 大连 116605) 摘 　要 :针对动态规划在 0 - 1背包问题中求解最优值时的教学难度 ,结合教学过程和特点 ,对计算最优 值的算法进行了改进 ,在与最优值递归公式保持一致的情况下简化了迭代过程 ,消除算法技巧 ,增加了算 法的规范性和连贯性 ,收到了理想的教学效果 。 关键词 :算法 ;动态规划 ; 0 - 1背包问题 中图分类号 : G642. 0　　　文献标志码 : A Teach in g Exp lora tion in D ynam ic Programm in g for Solv in g the 0 - 1 Knap sack Prob lem L I Zh i - j ie, ZHENG Ha i - xu (Co llege of Comp uter Science Engineering, D alian N ationalities U n iversity, D alian L iaon ing 116605, Ch ina) A b stract: Given all the difficu ltie s in teach ing abou t u sing dynam ic p rogramm ing to find the op tim al value for the 0 - 1 knap sack p rob lem , we imp roved the algorithm for op tim al value calcu la tion in comb ination w ith the p roce ss and characteristic s of teach ing. W ith the con sistence w ith the recu rsive form u la for the op tim al value m ain tained, we simp lified the iterative p roce ss and removed algorithm sk ills, thereby increa sing the comp liance and the coherence of the algorithm and hence receiving better teach ing re su lts. Key words: algorithm ; dynam ic p rogramm ing; the 0 - 1 knap sack p rob lem 　　算法设计与分析是一门集应用性 、创造性及 方法为 :枚举物品集合的所有子集 ,并选择那个具 实践性为一体的综合性极强的课程 [ 1 - 2 ] 。利用算 有最高效用且不超过背包负重 c 的子集 ,穷举法 法求解问题 ,首先要把实际问题抽象成数学模型 ,