"贪心算法实验二报告：最短路径与背包问题解决方案"

实验二 贪心选择算法姓名 ： 田圆圆 学号： 2013125135 一、实验目的与要求： 本次实验的主要目的是为了让学生理解贪心选择算法的思想。贪心选择算法的思想主要包括两个方面：一是贪心选择能得到问题的最优解，需要证明已选择的第一步一定包含在一个最优解之中；二是在做出第一步贪心选择后剩下的子问题应该有着类似的规模，可以用数学归纳法来证明贪心选择能得到问题的最优解。 二、预习与准备： 在进行实验之前，首先需要对贪心选择算法的思想进行预习和准备。贪心选择算法所涉及到的内容主要包括：贪心选择思想的具体实现，以及数学归纳法的运用。只有对这些内容进行了深入的学习和理解，才能够更好地完成本次实验任务。 三、实验题目： 1. 在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0到其余各点的最短路径。 2. 背包问题：给定 n 种物品和一个背包，物品 i 的重量是 Wi，其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 3. 多机调度问题：要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成。 四、实验过程： 1. 用贪心算法求解单源最短路径问题。具体步骤包括： （1）初始化：将源点到其余顶点的距离初始化为无穷大，源点到自身的距离初始化为0。 （2）贪心选择：依次从尚未确定最短路径的顶点中选择一个距离最短的顶点 u，并且将顶点 u 加入最短路径的集合 S 中。 （3）更新距离：对于所有与顶点 u 相连的顶点 v，如果通过顶点 u 的路径比当前路径短，则更新顶点 v 的距离。 （4）重复步骤（2）和步骤（3），直到所有顶点都被加入最短路径的集合 S 中。 2. 用贪心算法解决背包问题。具体步骤包括： （1）根据物品的单位重量价值进行排序。 （2）依次选择单位重量价值最大的物品加入背包，直到背包容量用完为止。 3. 用贪心算法解决多机调度问题。具体步骤包括： （1）根据作业的加工时间或者加工量进行排序。 （2）依次将作业分配给空闲的机器，尽量让每台机器的加工时间保持平衡。 五、实验总结： 通过本次实验，我对贪心选择算法的思想有了更深入的理解，并且掌握了贪心选择算法的具体应用。同时，我也意识到贪心选择算法在解决一些问题时可能会出现局部最优解而非整体最优解的情况，因此在使用贪心选择算法时需要谨慎选择应用场景。希望通过今后的学习和实践，能够更加熟练地掌握贪心选择算法并且灵活运用到实际问题中去。