贪婪算法是解决最优化问题的一种基本方法。它采用逐步构造最优解的思想,在问题求解的每一个阶段,都作出一个在一定标准下看上去最优的决策;决策一旦作出,就不可再更改。制定决策的依据称为贪婪准则。贪婪算法需要考虑以下步骤:
1 、明确问题的求解目标。
2 、分析问题所包含的约束条件。
3 、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。
4 、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后,就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪婪算法解决最优化问题的关键,它关系到问题能否得到成功解决及解决质量的高低。
接下来列举一些具体的例子: 例 1 : 计算发放工资时所需的最少人民币张数。输入数据为职工的工资数。要求统计并输出应发给该职工面值 100 元、 50 元、 20 元、 10 元、 5 元、 2 元、 1 元的人民币各多少张,使总张数最少。
分析:为了使总张数最少,那么最大面额的数量就会尽量的多。
例 2 : 旅行家的预算( 1999 年全国青少年信息学(计算机)奥林匹克分区联赛高中组复赛试题第三题)
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 d1 、汽车油箱的容量 c (以升为单位),每升汽油能行驶的距离 d2 、出发点每升汽油的价格 p 和沿途油站数 n ( n 可以为零),油站 i 离出发点的距离 di 、每升汽油的价格 pi ( i=1,2, ……n )。
计算结果四舍五入至小数点后两位。
如果无法到达目的地,则输出 “No solution” 。
输入描述
输入数据可能有多行:
第1行:
D1:两个城市之间的距离;C:汽车油箱的容量;D2:每升汽油能行驶的距离;P:出发点每升汽油价格;N:沿途油站数
第2到n+1行,共n行,依次表示各个加油站信息,每行有两个数据:第i+1行表示第i个油站,离出发点的距离Di;每升汽油价格Pi
输出描述
输出共一行:表示最小费用,四舍五入至小数点后两位。
如果无法到达目的地,则输出“No solution”。
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出样例
26.95
程序代码:写程序的时候本来考虑用当前最小的油价到尽可能远的距离,不一定到某一个站点,可以在站点和站点之间,然后再取第二大的油价判断可以到哪里,这个需要牵扯到邮箱容量什么的。比较复杂。后来发觉只能用下面的简单一点的贪婪法计算了。
package com.fnk.acm;
import java.text.DecimalFormat;
import java.util.ArrayList;
public class GreedyMinCost {
private double cityDistance = 275.6; // 两座城市之间的距离
private double capacity = 11.9; // 汽车油箱的容量
private double disCanMoveEveryUnit = 27.4; // 每升汽油能行驶的距离
private double priceInStartCity = 2.8;// 出发点每升汽油价格
//private int NumOfOieStation = 2;// 沿途油站数
private ArrayList<OilStation> osArray = new ArrayList<OilStation>();
public GreedyMinCost() {
osArray.add(new OilStation(102.0, 2.9));
osArray.add(new OilStation(220.0, 2.2));
//将终点加到next location列表里面
osArray.add(new OilStation(cityDistance, -1));
}
class OilStation {
private double distance;// 离出发点的距离
private double price;// 每升汽油价格
public OilStation(double distance, double price) {
this.distance = distance;
this.price = price;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public double getPrice() {
return price;
}
public void setPrice(double price) {
this.price = price;
}
}
public double getMinCost(){
double bestPrice = priceInStartCity;
double currentPostion = 0;
double cost = 0;
for(int j = 0 ; j < osArray.size();j ++ ){
for(int i = j; i <osArray.size(); i ++){
//根据贪婪算法判断当前的油价可以到的最远的距离。如果距离方面不超出,尽可能用油价低的油到尽可能远的加油站
if(bestPrice > osArray.get(i).price || disCanMoveEveryUnit * capacity + currentPostion < osArray.get(i).getDistance()){
if(i == j)
return -1;
cost += bestPrice * (osArray.get(i).getDistance() - currentPostion) / disCanMoveEveryUnit;
bestPrice =osArray.get(i).price;
j=i -1;
currentPostion = osArray.get(i).getDistance();
break;
}
}
}
return cost;
}
public static void main(String[] args){
GreedyMinCost gmc = new GreedyMinCost();
//用于四舍五入
DecimalFormat df = new DecimalFormat("#.00");
double minCost = gmc.getMinCost();
if(minCost <0 )
{
System.out.println("No Solution!");
}
else{
System.out.println(df.format(minCost));
}
}
}
分享到:
相关推荐
贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好...在学习和理解贪婪算法时,通过分析和比较其与动态规划等其他算法的差异,可以更好地掌握其适用范围和局限性。
在压缩包“贪婪算法”中,可能包含了实现这些步骤的易语言源代码文件,供学习者参考和学习。通过分析和理解这些源码,可以深入理解贪婪算法的原理和易语言的编程技巧,进一步提升编程能力。 总结来说,贪婪算法是一...
贪婪算法是计算机科学中一种重要的算法思想,常用于求解优化问题。在处理问题时,它遵循“每一步都采取当前看起来最优的选择”这一原则,即局部最优解,期望通过一系列局部最优解来达到全局最优解。然而,贪婪算法并...
### 贪婪算法在分页式存储管理中的应用 #### 实验背景与目的 本实验旨在通过编写一个模拟分页式存储管理程序,帮助学习者深入理解分页式存储管理的基本概念及其实现方法。实验重点是实现最近最久未使用(LRU)页面...
贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法策略。它通常用于解决优化问题,尤其是在时间或空间复杂度上需要高效求解的问题。贪婪算法的核心...
贪婪算法是一种在每一步...对于初学者来说,深入学习和理解这些概念,通过阅读PPT文件(如Chapter13-贪婪算法-1.ppt、Chapter13-贪婪算法-2.ppt、普里姆算法.ppt)将有助于深化对贪婪算法及其在数据结构中应用的理解。
贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的...通过学习和掌握贪婪算法,你将能够解决一类重要的优化问题,并在MATLAB编程中实现这些解决方案。
本篇文章将深入探讨标题和描述中提到的一些核心算法,包括动态规划、分治算法、概率算法、模拟退火算法、搜索算法、贪婪算法、在线MATLAB应用、遗传算法以及组合算法。 1. **动态规划**:动态规划是一种解决具有...
《OFDM系统中的贪婪算法应用解析》 在无线通信领域,正交频分复用(Orthogonal Frequency Division Multiplexing,简称OFDM)技术因其高效频谱利用率和抗多径衰落的优势,被广泛应用于现代通信系统,如4G、5G以及Wi...
总的来说,这个MATLAB代码提供了学习和实践贪婪算法的一个平台,对于参与数学建模或对算法感兴趣的同学们来说,是一个宝贵的资源。通过分析和修改这段代码,你可以深入理解贪婪算法的工作原理,并提升自己的编程能力...
贪婪算法和模拟退火算法的体会心得
在图像处理领域,贪婪算法(Greed Algorithm)如匹配 pursuit(MP)被广泛应用于图像的稀疏表示和重构。这个过程旨在用尽可能少的基函数来表示原始图像数据,从而达到压缩存储、降噪和特征提取的目的。MP算法是一种...
总的来说,贪婪算法、遗传算法和Floyd算法在解决不同类型的优化问题上各有优势,而"算法演示系统"则提供了一个直观的学习和实践平台。通过MATLAB的实例,我们可以深入学习这些算法的原理,掌握它们的实现方法,...
总的来说,“贪婪算法.rar”这个压缩包很可能包含了关于贪婪算法的基本概念、算法流程、应用场景和实例分析,对于学习和理解贪婪算法来说是非常有价值的资料。通过深入学习这些内容,你可以更好地掌握如何运用贪婪...
### 计算机算法——贪婪算法详解 #### 引言 在计算机科学领域,算法设计是一种核心技能,它...通过对贪婪算法的深入学习,我们可以更好地把握其精髓,从而在实际问题中灵活运用,创造出更加高效、实用的解决方案。
基于贪婪算法的自动排课表系统研究与实践 排课表系统是高校管理中极其重要的一项工作,它直接关系到学生的学习安排和教师的教学计划。然而,由于涉及的专业、课程、教师、学生以及教室资源等众多因素,高校排课表...
标题中的“beibao.rar”是一个压缩包文件,其中包含了关于“背包问题”的解决方法,主要使用了“贪婪...通过学习和理解这些代码,读者不仅可以掌握贪婪算法的原理,还能了解如何在实际问题中应用MATLAB进行算法开发。
这个压缩包“tanlansuanfa.rar”包含了关于贪婪算法的详细讲解,很适合对ACM算法竞赛感兴趣的学生学习。 贪婪算法的核心思想是局部最优解,它在每一步选择中都采取当前状态下最好的选择,而不考虑长远的后果。然而...