实验二 贪心选择算法
姓名 ： 田圆圆
学号：2013125135
一、实验目的与要求： 理解贪心选择算法的思想。
二、预习与准备：贪心选择算法思想：
（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在
一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。
（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的
子问题 为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。
三、实验题目：
1.在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0
到其余各点的最短路径。
2.背包问题
给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量
为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
3.多机调度问题
要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机
器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前
不允许中断处理。作业不能拆分成更小的子作业。
剩余18页未读，继续阅读
资源评论
