目录
实验 2《贪心算法实验》
一、实验目的
二、实验内容
三、算法思想分析
贪心法的原理：
贪心算法常用解题方法：
贪心算法存在以下问题：
实验中具体的贪心算法分析：
四、实验过程分析
遇到的问题及解决
实验体会
改进空间
五、算法源代码及用户屏幕
1.单源最短路径：
2.找零：
3.多机调度：
实验 2《贪心算法实验》
一、实验目的
- 了解贪心算法思想
- 掌握贪心法典型问题，如背包问题、作业调度问题等。
二、实验内容
- 编写一个简单的程序，实现单源最短路径问题。
- 编写一段程序，实现找零。
【问题描述】当前有面值分别为 2 角 5 分，1 角，5 分，1 分的硬币，请给出找 n 分钱的最佳方案（要求找出的硬币数目最少）。 - 编写程序实现多机调度问题
【问题描述】要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
三、算法思想分析
贪心法的原理：
- 贪心选择性质：所求问题的整体最优解可通过一系列局部最优的选择，即贪心选择来实现；
- 最优子结构性质：原问题的最优解包含子问题的最优解
贪心算法常用解题方法：
常用自顶向下的方式进行，步骤：
- 套用问题模型：事先定义了限制条件和期望值的一组数据，在满足限制的条件下，使期望值最大；
- 贪心算法：每次选择对限制值同等贡献量的情况下对期望值贡献最大的数据；
- 举例验证。
贪心算法存在以下问题：
- 不能保证给出的是最优解；
- 不能用来求最大/小解问题；
- 只能求满足某些约束条件的可行解的范围
实验中具体的贪心算法分析：
1、单源最短路径：限制条件——单源；期望值——总权值最小。
采用Dijkstra算法，设置顶点集合S并不断地作贪心选择来扩充这个集合，直到该集合包含所有顶点。一个顶点属于集合S当且仅当从源到该顶点的最短路径已知。
2、找零：限制条件——共n分钱；期望值——找的硬币数目最少。
不断做出贪心选择——选择符合要求的面值最大的硬币，直到找了n分钱为止。
3、多机调度：限制条件——m台机器；期望值——让作业在尽可能短的时间内加工完成。
当n > m时，先对作业按要求的执行时间从大到小排序，然后按照这个排好序的顺序，去找目前用时最短的机器，并将该机器加上对应时长，最后取那个使用时间最长的机器所用时间为最优解。
四、实验过程分析
-
遇到的问题及解决
- 刚开始我在想这个有向图是应该自己定义还是让用户输入呢，让用户从控制台输入的话比较麻烦，但是考虑到程序的通用性，还是选择多花点心思来让用户通过控制台输入数据来创建有向图，从而使得程序可以方便地求出不同有向图中的最短单源路径，且作为单源的这个顶点也是可以由用户自己选择的。
- 单源最短路径中通过比较，如果dist[j] + cost[j][i] < dist[i]，则更新dist[i]为dist[j] + cost[j][i]，从而得到source到i的最短路径，但是由于两个顶点之间如果没有路径可达，我将权值赋为了inf，此时随便加一个数将产生溢出！这也是后面出错了原因，虽然逻辑并没有问题，但结果却一直不对，于是我跟踪调试，最终找到问题所在。加入判断条件后执行正确
- 找零中刚开始我一直在想题目是不是少给了条件，没说每种面值的硬币分别有多少个，后来想了想应该是默认每种面值都有足够多的硬币数，不然n也没有范围限制，不一定能凑齐n分钱，如果是这样的话，找零的实现还是挺简单的。
- 多机调度问题中刚开始没有理解题目意思，没搞懂这个尽可能短的时间是什么意思，还停留在操作系统的学习内容中，在想是指所有作业的等待时间最短，让所有作业的平均周转时间最短吗，那这跟贪心有什么关系呢。后来重读题目发现这个机器应该就是指的CPU，所以是通过合理的调度，让每个CPU都一直运转，不能停下来，即让它们的执行时间尽可能平均分配，这样的话整体的时间就最短了。那么转化为贪心选择就是将作业不停地分配给快要执行结束的CPU，让它不能停下来。至于作业的调度顺序我觉得应该是先来先服务，只要有作业到了就分配给CPU。但是后来看了PPT发现是将作业先排序，从用时最长的开始分配。这里的作业应该都是同时到达的，没有先后一说，不用考虑那么复杂。
- 多机调度的关键贪心策略是最长处理时间作业优先，随时将此时的时间最大工作交给目前用时最短的机器，达到了尽可能的使总用时最短。
-
实验体会
贪心算法与分治的共同点在于它们其实都是通过降低问题规模来一步一步解决问题，都要求有最优子结构性质，除此之外，贪心还有一个要求，就是要具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这个要求其实是很高的，所以实际生活中并没有很多问题可以通过贪心算法来找到最优解，但是通过贪心来近似寻找最优解是一个很巧妙的想法，就如本次实验中的多机调度问题，它本来是一个NP完全问题，即一个多项式复杂程度的非确定性问题，但是通过使用贪心选择策略我们能设计出较好的近似算法。
总之，明白贪心的优缺点后，我们可以进行适当的舍取，确定自己是否要用贪心来解决遇到的问题，如果用贪心的话可能会出现什么问题。
-
改进空间
- 与上次实验一样，算法实验我主要将注意力集中在各种算法的思想及其实现上，对于程序的健壮性并没有特别考虑，如单源最短路径实验中只是将作为源的顶点判断了一下是否在顶点集中，因为我认为这一点可能较为容易出错，因为程序中顶点是从0开始排序的，但是有时可能误以为从1开始，从而导致出错。其他地方全靠用户自己输入是否正确，程序并未进行相关检查。因为检查起来太麻烦了，感觉也不是很有必要，但是在正式项目开发中，对程序的健壮性是有严格要求的，所以这里仍然是应该改进的地方。
- 对于算法的时间复杂度其实是可以进一步优化的，比如在多机调度中我使用了在实验一中实现的快排，而不是用一个嵌套循环来进行选择排序，一定程序上提高了效率。在单源最短路径中由于判断逻辑较为复杂，用到了很多循环及判断语句，这些地方都是可以进一步优化的，可以仔细思考，用更为灵活的方式来进行处理，从而提高程序执行效率。
五、算法源代码及用户屏幕
1.单源最短路径：
源代码：
import java.util.Scanner;
public class Dijkstra {
private static int inf = Integer.MAX_VALUE;//无穷大
private static int[][] cost;//邻接矩阵，存储权值
private static int source;//单源顶点，即求source到各顶点的最短路径
private static int n;//顶点个数
private static String [] path;//存储最短路径经过的点
private static int []dist;//存储当前最短路径的值
private static boolean []already;//存储顶点是否已找出最短路径
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请输入图中顶点个数：");
n = input.nextInt();
cost = new int[n][n];//初始化邻接矩阵为无穷大
dist = new int[n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cost[i][j] = inf;
}
}
System.out.print("您的图中所有顶点为：");
for(int i = 0; i < n ; i++){
System.out.print(i+" ");
}
System.out.print('
');
System.out.println("请输入图中的各有向边及其权值（如“1 2 10”表示一条从1到2的有向边，其权值为10）每一行表示一条有向边，输入-1表示结束：");
int i = input.nextInt();
int j = input.nextInt();
while (i != -1){
cost[i][j] = input.nextInt();
input.nextLine();//吸收换行符
i = input.nextInt();
if(i != -1) j = input.nextInt();
}
for(i = 0; i < n; i++){//自己到自己的距离为0
cost[i][i] = 0;
}
System.out.println("该有向图的邻接矩阵如下：");
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(cost[i][j] == inf){
System.out.print("inf" + " ");
}else {
System.out.print(cost[i][j] + " ");
}
}
System.out.print('
');
}
System.out.print("请输入您选择的初始顶点：");
source = input.nextInt();
if(source < 0 || source > n - 1){
System.out.println("输入非法！该顶点不在图中！");
return;
}
dist[source] = 0;//自己到自己的距离为0
already = new boolean[n];
already[source] = true;//源顶点到自己的最短路径是0
path = new String[n];
for(i = 0; i < n; i++){
path[i] = source + "->" + i;
}
getPath();
for(i = 0; i < n; i++){
System.out.println("path: " + path[i] + ": " + dist[i]);
}
}
private static void getPath(){//设为类的成员了，可以不用传参
//初始dist数组
for(int i = 0 ; i < n; i++){
dist[i] = cost[source][i];
}
for(int i = 0; i < n; i++){
updateDist();
getMinDistToAlready();
printDist();
}
}
private static void updateDist(){//更新dist数组
//如果dist[j] + cost[j][i] < dist[i]，则更新dist[i]为dist[j] + cost[j][i]-----得到source到i的最短路径
for(int i = 0; i < n; i++){
if(!already[i]){
for(int j = 1; j < n; j++){
if(already[j] && cost[j][i] != inf && dist[j] + cost[j][i] < dist[i]){
dist[i] = dist[j] + cost[j][i];
path[i] = path[j] + "->" + i ;
}
}
}
}
}
private static void getMinDistToAlready(){
//找出dist中的最小值，加入already中，并更新其path
int min = inf;
int minIndex = -1;//最小值是到哪个顶点
for(int i = 0; i < n; i++){
if(already[i] == false && dist[i] < min){//只判断还未找出最短路径的顶点
min = dist[i];
minIndex = i;
}
}
if(minIndex != -1)already[minIndex] = true;
}
private static void printDist(){//用于检测算法执行有没有问题
System.out.print("dist: ");
for(int i = 0 ; i < n; i++){
System.out.print(dist[i] + " ");
}
System.out.println();
}
}
2.找零：
源代码：
import java.util.Scanner;
public class Change {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n;//要找n分钱
System.out.print("请输入要求找的数目（以分为单位, 要求为整数）: ");
n = input.nextInt();
int[] coin = {25, 10, 5, 1};
int count = 0;//记录找了几个面值相同的硬币
for(int i = 0; i < 4; i++){
while (n >= coin[i]){
n -= coin[i];
count ++;
}
System.out.println(coin[i] + "分的硬币：" + count + "个");
count = 0;
}
}
}
3.多机调度：
源代码：
import java.util.Scanner;
public class JobScheduling {
private static int[] cpu;//当前每台机器处理时间
private static int[] time;//每个作业所需处理时间
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请分别输入作业数和机器台数：");
int n = input.nextInt();
time = new int[n];
int m = input.nextInt();
cpu = new int[m];
System.out.print("请输入" + n + "个正整数，分别表示每个作业所需的处理时间：");
int count = 0;//统计总共要运行多少时间，用于检验程序运行结果的正确性
for(int i = 0; i < n; i++){
time[i] = input.nextInt();
count += time[i];
}
System.out.println("共计" + count);
if(n <= m){//此时每个作业可以分配到一台机器上处理，最短用时即为运行时间最长的作业所需时间
for(int i = 0; i < n; i++){
cpu[i] = time[i];
}
System.out.println("最短用时为" + getMax() + "
各机器用时分别为：");
for(int i = 0; i < m; i++){
System.out.println("第" + (i + 1) + "台机器运行时长为" + cpu[i]);
}
}else {//如果作业数多于机器，则要将作业排序，再从大到小分配给机器
QuickSort.quickSort(time, 0, n - 1);//利用之前写的快排来将time排序，不过需要注意的是此处是从小到大排的，所以分配的时候要从最后一个开始往前分配
for(int i = 0; i < m; i++){
cpu[i] = time[n - 1 - i];//先将每一台机器都分配一个作业（从最长的作业开始分配）
}
for(int i = m; i < n; i++){
int min = getMin();//找出当前运行时间最短的机器，将作业分配给它
cpu[min] += time[n - i -1];
}
System.out.println("最短用时为" + getMax() + "
各机器用时分别为：");
for(int i = 0; i < m; i++){
System.out.println("第" + (i + 1) + "台机器运行时长为" + cpu[i]);
}
}
}
private static int getMax(){
int max = 0;
for(int i = 0; i < cpu.length; i++){
if(cpu[i] > max){
max = cpu[i];
}
}
return max;
}
private static int getMin(){
int min = cpu[0];
int minIndex = 0;
for(int i = 0; i < cpu.length; i++){
if(cpu[i] < min){
min = cpu[i];
minIndex = i;
}
}
return minIndex;
}
}