中 南 大 学
《算法设计与分析》实验报告
姓 名：
专 业 班 级：
学 号：
指导教师：
完成日期： 20010.1
一．实验名称
贪心算法实验
二． 实验目的
1. 了解贪心算法思想
2. 掌握贪心法典型问题，如背包问题、作业调度问题等。
三．实验内容
1. 编写一个简单的程序，实现单源最短路径问题
2. 编写一段程序，实现找零
3. 编写程序实现多机调度问题
四．算法思想分析
1.单源最短路径问题
（1）问题描述
已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。
（2）算法分析
Dijkstra算法：
算法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。
2.找零问题
（1）问题描述
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少） （2）问题分析计算法实现
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
假如要找77分钱，有上面的面值分别为25，10，5，1的硬币数，为了找最少的硬币数，那么他是不是该这样找呢，先看该找多少个25分的， 57／25＝2，好像是2个，要是3个的话，我们还得再给老板一个1分的，这样不行，那么只能给2个25分的，由于还少给27，所以还得给我2个10分的，1个5分的和2个1分。
Harbin Institute of Technology
Page 1 of 5 Designed by 谢浩哲 「算法设计与分析」第4章作业
2015.10
学号: 15S103172 姓名: 谢浩哲
1. 给定字符串s和字典dict, 判断s能否划分成由dict中单词组成的序列. 例如, s = “helloworld”,
dict={“hello”, “world”}, 返回True因为s可以被划分为“hello world”; 若不能, 则返回
false.
使用数组isMatched[i]表示字符串s[0, i - 1]是否可以被划分.
因此isMatched[s.length]表示字符串s是否可以被划分.
若isMatched[i] == true, 表示s[0, i - 1]可以被划分, 则需要同时满足如下条件之一:
isMatched[0] == true, 且s[0, i - 1]在dict中
isMatched[1] == true, 且s[1, i - 1]在dict中
isMatched[2] == true, 且s[2, i - 1]在dict中
…
isMatched[i - 1] == true, 且s[i - 1, i - 1]在dict中 1 import java.util.Set;
2 3 public class Solution {
4 public boolean wordBreak(String s, Set wordDict) { 5 int length = s.length();
6 boolean[] isMatched = new boolean[length + 1];
7 isMatched[0] = true;
8 9 for ( int i = 1; i <= length; ++ i ) {
10 for ( int j = 0; j < i; ++ j ) {
计算机算法设计与分析第4版(王晓东著)课后答案下载
计算机算法设计与分析第4版内容简介
第1章 算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章 递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序 2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。为突出教材的`可读性和可用性，章首增加了学习要点提示，章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。
列举贪心算法求解的经典问题
贪心算法是一种基于贪婪策略的算法，它在每一步选择中都采取当前状态下的最优决策，以期望能够得到全局最优解。以下是一些常见的经典问题，可以通过贪心算法来求解：
1. 零钱兑换问题（Coin Change Problem）：给定一些不同面额的硬币和一个要兑换的金额，找出使用最少的硬币数量来凑成该金额的方法。
2. 区间调度问题（Interval Scheduling Problem）：给定一组区间，每个区间都有开始时间和结束时间，目标是找到最大的不重叠区间子集。
3. 活动选择问题（Activity Selection Problem）：给定一组活动，每个活动都有开始时间和结束时间，目标是安排尽可能多的活动，使得它们不重叠。
4. 霍夫曼编码（Huffman Coding）：给定一组字符及其出现频率，通过构建霍夫曼树来生成最优的编码方案，使得出现频率高的字符具有较短的编码。
5. 最小生成树（Minimum Spanning Tree）：给定一个连通图，找到一个子图，使得它包含了所有的顶点且边的权重之和最小。
6. 最短路径问题（Shortest Path Problem）：给定一个图和起点，找到从起点到其他顶点的最短路径，其中边的权重可以是正数、负数或零。
这些问题都可以通过贪心算法求解，但需要注意的是，贪心算法并不总是能得到全局最优解，因此在使用贪心算法时要仔细分析问题的性质，确保贪心策略的正确性。
