《算法分析与设计》作业答案.doc

《算法分析与设计》作业答案涉及到的主要知识点包括：贪婪算法、二分图覆盖问题以及分而治之的策略。 1. 贪婪算法在连续背包问题中的应用： - 连续背包问题是一个优化问题，目标是在给定容量限制下，最大化物品的总价值。 - 提供的贪婪策略是按价值密度（价值/重量）非递减的顺序选取物品，尽可能装入背包。 - 在给定的例子中，n=3，物品重量w=[100,10,10]，价值p=[20,15,15]，背包容量c=105。按照贪婪策略，先装入价值密度高的物品，即w2和w3，它们共重20，剩余容量为85。w1的部分可以装入0.85，因此总价值为47。 2. 二分图覆盖问题： - 二分图覆盖问题寻找的是最小顶点覆盖，即最少数量的顶点可以覆盖所有的边。 - 提供的算法在A和B两部分顶点中，每次选择未覆盖边最多的顶点进行覆盖，直到所有顶点都被覆盖或无法再覆盖为止。 - 证明了当二分图无覆盖时，该算法无法找到覆盖；反之，若有覆盖，算法总能找到最小覆盖。 - 示例展示了即使有覆盖，特定情况下算法可能找不到最小覆盖。 3. 另一种贪婪启发式算法： - 这种算法优先选择能覆盖B中更多未被覆盖顶点的A中顶点。 - 伪代码描述了如何逐步构建覆盖，优先处理入度为1的顶点，然后选择未被覆盖边最多的顶点。 4. 分而治之策略解决找假币问题： - 分而治之是一种解决问题的方法，将大问题分解成小问题，分别解决后组合成原问题的解。 - 伪代码描述的算法可能是：将n个硬币分为两组，每组大约n/2，称量这两组，确定假币在其中一组；然后对包含假币的组重复此过程，直至找到假币。 - C程序实现会涉及循环和条件判断，根据称量结果分割硬币并递归处理，直到找出假币。 以上就是《算法分析与设计》作业中涉及的主要算法和理论，这些内容涵盖了贪心策略、图论中的覆盖问题以及分治法的应用。理解并掌握这些知识点对于学习和解决实际问题具有重要意义。