2021秋计软实验：贪心算法实践——背包问题与哈夫曼编码

"本实验旨在通过编程实践，让学生深入理解和掌握贪心算法在计算机科学中的应用，特别是针对背包问题和哈夫曼编码问题。首先，实验涉及到的是背包问题，它是一个经典的优化问题，分为分数背包问题和01背包问题。分数背包问题允许物品进行分割，通过计算每个物品的价值与重量的比例，按比例选取物品，直至背包满载且总价值最大化。例如，实验中给出了一个含有7个可分割物品的实例，要求学生设计贪心算法求出在给定容量下物品的最优组合及其总价值。 另一方面，01背包问题更现实，物品不可分割，只能选择或不选择，同样需要找出在容量限制下的物品组合，以获得最大价值。实验要求确定每个物品是否应放入背包以及总价值，考验了学生对非可分割资源管理的理解。 接着，实验引入了哈夫曼编码问题，这是信息编码领域的一个关键概念，利用贪心策略来构建基于字符频率的最短编码。哈夫曼树在此过程中起着核心作用，通过不断合并频率最低的字符，形成一棵平衡的二叉树，从而得到每个字符的最优编码。实验要求学生运用贪心算法构建哈夫曼树，并计算加权路径长度，以实现编码的最短化。 这个实验涵盖了贪心算法的核心思想——局部最优解的全局最优，让学生在实际操作中体验如何通过每一步的最优决策，逐步逼近问题的整体最优解。通过解决这些实际问题，学生不仅能提升编程技巧，还能加深对贪心算法原理的深入理解。"