说到“贪”字,很邪恶的一个词,记得和珅和大人拆解过这个字,为”今“和”贝“,而”贝“字分解成”上面的那个XX“和”人“,意思就是说
今天你贪了,明天一座监狱就把你套起来,纵观古今,有多少豪杰与"贪“结下了不解之缘,呵呵,扯远了。
这个贪心的行为在算法中也成为了一种指导思想,也就是说贪心算法所作出的选择在当时的环境下是最好的,说深一点就是它只是某种
意义上的局部最优解,但不一定是全局最优解,此时往往接近于最优解。
一: 优点
前面也说了,贪心只是求的当前环境下的最优解,而不是追究整体的最优解,所以贪心就避免了为求的整体最优解而枚举各种方案所
耗费的时间。
二: 问题
① 不能保证贪心所得出的解是整体最优的。
② 不能用来求最大解和最小解问题。
③ 只能求满足某些约束条件的可行解的范围。
三: 案例
其实说到贪心,基本上都会提到“背包问题”,这里我就举一个“找零钱的问题“,对的,找零钱问题是我们生活中一个活生生的贪心算法
的例子,比如我买了“康师傅来一桶方便面”,给了10两银子,方便面3.8两,那么收银mm该找我6.2两,现实中mm不自觉的就会用到贪心的行
为给我找最少张币,总不能我给mm一张,mm给我十几张,那样mm会心疼的。
此时mm提供的方案就是:5元1张,1元1张,2角1张。
闲话不说,上代码:
package com.jiaozg.algorithm.feibonaqie;
import java.util.Scanner;
import org.junit.Test;
public class Tanxin {
public void getChange(float money) {
int yuan100 = 0, yuan50 = 0, yuan20 = 0, yuan10 = 0, yuan5 = 0, yuan1 = 0, coin5 = 0, coin2 = 0, coin1 = 0;
/**
* 下面采用循环递减方式写demo
*/
while (money >= 100d) {
yuan100++;
money -= 100d;
}
while (money >= 50d) {
yuan50++;
money -= 50d;
}
while (money >= 20d) {
yuan20++;
money -= 20d;
}
while (money >= 10d) {
yuan10++;
money -= 10d;
}
while (money >= 5d) {
yuan5++;
money -= 5d;
}
while (money >= 1d) {
yuan1++;
money -= 1d;
}
while (money >= 0.5d) {
coin5++;
money -= 0.5d;
}
while (money >= 0.2d) {
coin2++;
money -= 0.2d;
}
while (money >= 0.1d) {
coin1++;
money -= 0.1d;
}
System.out.println("需找零:");
if (yuan100 > 0) {
System.out.println("100元 " + yuan100 + "张");
}
if (yuan50 > 0) {
System.out.println("50元 " + yuan50 + "张");
}
if (yuan20 > 0) {
System.out.println("20元 " + yuan20 + "张");
}
if (yuan10 > 0) {
System.out.println("10元 " + yuan10 + "张");
}
if (yuan5 > 0) {
System.out.println("5元 " + yuan5 + "张");
}
if (yuan1 > 0) {
System.out.println("1元 " + yuan1 + "张");
}
if (coin5 > 0) {
System.out.println("5角 " + coin5 + "张");
}
if (coin2 > 0) {
System.out.println("2角 " + coin2 + "张");
}
if (coin1 > 0) {
System.out.println("1角 " + coin1 + "张");
}
}
@Test
public void testTanxinSuanFa() {
while (true) {
System.out.println("请付款(精确到1角):");
Scanner scanner = new Scanner(System.in);
float money = scanner.nextFloat();
getChange(money);
}
}
}
输出结果:
请付款(精确到1角):
1688.8
需找零:
100元 16张
50元 1张
20元 1张
10元 1张
5元 1张
1元 3张
5角 1张
2角 1张
1角 1张
但是我发现了一个问题,如果输入78.6的话,输出是不对的
78.6
需找零:
50元 1张
20元 1张
5元 1张
1元 3张
5角 1张
请付款(精确到1角):
少了一角,debug发现和一角比较的时候,那个数编程0.099999999999,所以一角就没有输出
这个问题的详细说一下
小数精确计算
System.out.println(2.00 -1.10);//0.8999999999999999
上面的计算出的结果不是 0.9,而是一连串的小数。问题在于1.1这个数字不能被精确表示为一个double,因此它被表示为最接近它的double值,该程序从2中减去的就是这个值,但这个计算的结果并不是最接近0.9的double值。
一般地说,问题在于并不是所有的小数都可以用二进制浮点数精确表示。
二进制浮点对于货币计算是非常不适合的,因为它不可能将1.0表示成10的其他任何负次幂。
解决问题的第一种方式是使用货币的最小单位(分)来表示:System.out.println(200-110);//90
第二种方式是使用BigDecimal,但一定要用BigDecimal(String)构造器,而千万不要用BigDecimal(double)来构造(也不能将float或double型转换成String再来使用BigDecimal(String)来构造,因为在将float或double转换成String时精度已丢失)。例如new BigDecimal(0.1),它将返回一个BigDecimal,也即0.1000000000000000055511151231257827021181583404541015625,正确使用BigDecimal,程序就可以打印出我们所期望的结果0.9:
System.out.println(new BigDecimal("2.0").subtract(new BigDecimal("1.10")));// 0.9
另外,如果要比较两个浮点数的大小,要使用BigDecimal的compareTo方法。
参考:http://blog.csdn.net/m13666368773/article/details/7531473
分享到:
相关推荐
运用贪心策略解决0 1背包问题 void beibao(int *w,int *v,int *x,int n,int *C) { int i,j,temp; for(i=0;i;i++) for(j=i+1;j;j++) if(v[i]/w[i][j]/w[j]) { temp=v[i]; v[i]=v[j]; v[j]=temp...
算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,尤其是java代码简直如大海捞针。因此,做完...
用面向对象的程序设计思想自己动手写压缩软件,采用了优先队列这一很好的数据结构实现的贪心算法构造Huffman树,能打印Huffman树,显示编码表,压缩文件和解压缩文件,采用UTF-8字符集,支持中文文件
给出100以内的任何数,然后50,10,5,1四个数找零钱方案
贪心算法、回溯算法、动态规划算法等思想实现的加油问题
在表达每一种技术时,阐述它的应用背景,强调每个算法运转背后的简洁数学思想,注意运用与其他技术类比的方法来说明它的特征,并提供了大量相应实际问题的例子。《国外经典教材·算法概论》同时也注重了对每一种算法...
数据结构和算法是计算机科学的核心基础,对于编程开发人员来说,掌握它们至关重要。以下是关于Java数据结构和算法的一些介绍: ...此外,算法设计中的一些基本思想,如递归、动态规划、贪心算法等,也是值得深入学习的。
.算法与数据结构基本概念 (1)数据、数据对象和数据结构 (2)抽象数据类型 (3)算法的特征及评价的标准 ...(2)贪心算法的思想 (3)回溯与分支限界算法的比较 (4)算法时间和空间复杂度的简单分析
采用贪心算法的思想解决八皇后问题,每步都取上一步的局部最优解
排序算法、动态规划、递归、回溯法、贪心算法等。 二、Java Java 基础概念 基本概念、面相对象、关键字、基本数据类型与运算、字符串与数组、异常处理、Object通用方法 Java 集合框架 数据结构 & 源码分析:...
贪心&动态规划 高级数据结构 树论基础&二叉树 二叉搜索树&红黑树 BTree Trie树&赫夫曼树 堆树 图论基础 最短路径 高效查找算法 二分&HashMap HashSet&TreeSet 索引技术 中文分词算法 Lucene 性能调优 JVM性能调优 ...
在自己思考的基础之上融入高手们的编程思想,做好详细记录。 如何写出正确的程序? 明确变量的含义 循环不变量 小数据量调试 大数据量的测试 时间复杂度分析与空间复杂度分析 增加一个文件夹leetcode,用于记录数据...
贪心算法 回溯算法 剪枝算法 动态规划 朴素贝叶斯 推荐算法 最小生成树算法 最短路径算法 并发 Java 并发 多线程 线程安全 一致性、事务 事务 ACID 特性 事务的隔离级别 MVCC 锁 Java中的锁和同步类 公平锁 & 非公平...
分别从蛮力法、动态规划法、贪心法这三种算法入手, 提出了求解投资问题的算法思想, 给出了算法的伪代码, 并对算法进行了分析比较.
邻接矩阵Prim算法Java实现,使用邻接矩阵储存结点和权值,利用贪心算法思想实现Prim算法,求得结点的最小生成树
用分治法思想解决比赛日程安排问题,Java语言描述。
采用贪心策略可以直接求得给定网络的最小生成树。 解析请参加教材115页。 实验方法: 使用贪婪法设计本问题的解决方案。 编成任务: 给定网络图,求其最小生成树。 Input 节点个数和给定网络图的邻接矩阵...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
leetcode怎么搜索好友 数据结构与算法之美 引言 : 数据结构是为算法服务的,...算法思想 贪心算法 高级篇 实战篇 推荐专栏 专栏导航 问题清单 array(数组) 算法题目 Two Sum(两数之和) LeetCode 1 题目 给定一个