中小学教育资源及组卷应用平台 第四单元挑战 使用二叉树解简单背包问题 教材分析 本节的主要内容是使用二叉树解简单背包问题。本项目开展的学习、讨论和实践，让学生体验分析问题、提炼方法、建立模型、优化策略的过程，进一步使用二叉树解决实际问题。提升信息意识，提高数据素养，肩负起信息社会责任，从容应对数据时代的各项挑战。 教学目标 1.了解二叉树的概念及其基本操作方法； 2.不同的物品排列顺序对构建二叉树的影响； 3.二叉树的构建； 教学重点 1.不同的物品排列顺序对构建二叉树的影响； 2.二叉树的构建； 教学难点 1.二叉树的构建； 教学方法 体验法、讲授法、讨论法、示例法 教学准备 计算机教室、多媒体设备、多媒体广播软件、教学课件、学生上机练习的程序文件等。 教学过程 一、新课导入 复习二叉树的基本操作，二叉树算术表达式转换为方便计算机处理的后缀表达式的方法以及二叉树如何构建。 二、项目任务 假设现有一个载重量最多为10千克的背包，以及5件物品。其中，第一件物品的重量和价值分别为了千克和9元；第二件物品的重量和价值分别为2千克和8元；第三件物品的重量和价值分别为4千克和7元；第四件物品的重量和价值分别为7千克和16元；第五件物品的重量和价值分别为6千克和15元。那么，此背包中可以放哪些物品，使得重量总和不超过10千克，而价值总和最大呢？ 请构建二叉树，列出所有可能的物品放置策略，并选出其中的最优策略(背包里所有物品的价值总和最大，比比哪一组的速度快。 三、项目指引 本项目求解的关键是，判断如果当前背包里的重量与下一件要放入物品的重量的和未超过重量限制，则放入下一件物品；超过重量限制，则不放入下一件物品，而后在两种情况下分别继续同样的判断，如此反复，直至考虑完所有物品。过程中的每一次判断相当于产生了两条策略路径，这与二叉树的树形很像，如图4-12所示。每一个分支结点都表示背包的一种状态，而叶结点表示得出的一种策略。每个结点的左孩子表示放入下一件物品的背包状态(一旦无法放下一件物品则无左孩子)，每个结点的右孩子表示不放入下一件物品的背包状态。 1.假设根结点为背包空的状态，画出二叉树。为方便计算和加快速度，将物品以重量、价值)的形式，按物品顺序从上到下排列在二叉树对应的每一层旁，思考物品的排列顺序对构建二叉树有何影响。 参考答案： 学生可以按照不同的排列顺序将五样物品依次放人背包，不同的排列顺序将构建出不同的二叉树，但列出的所有可能的物品放置策略的总数相同。 假设根节点为背包空的状态，若按照物品、物品2、物品3、物品4、物品5的次序放置，可画出如下二叉树(a)。 假设根节点为背包空的状态，若按照价值最大物品、价值次大物。...值最小物品的次序放置，可画出如下二叉树(b)。 写出最优策略。 参考答案： 装入第一件物品和第四件物品，重量总和为10千克，价值总和为25元。 （a） (b) 四、交流评价与反思 以自己熟悉的信息表达工具(如演示文稿等)制作电子作品，通过网络或课堂展示交流构建的二叉树和求得的最优策略。并对他人的作品进行评价。 21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页） HYPERLINK "http://21世纪教育网(www.21cnjy.com) " 21世纪教育网(www.21cnjy.com)(
课件网) 使用二叉树解简单背包问题 信息技术沪教版 选择性必修1 第四单元挑战 一、新课导入 二、项目任务 三、项目指引 四、交流评价与反思 一、新课导入 二叉树的基本操作主要有二叉树的创建、二叉树的遍历、求二叉树的深度等。其中二叉树的遍历方法主要有以下几种。 ①先序遍历：先访问二叉树根结点，然后先序遍历左子树，再先序遍历右子树。 ②中序遍历： ... ...
