浅析java贪心算法

贪心算法的基本思路

1.建立数学模型来描述问题。　

　2.把求解的问题分成若干个子问题。　

　3.对每一子问题求解，得到子问题的局部最优解。　

　4.把子问题的解局部最优解合成原来解问题的一个解。　

　实现该算法的过程：　

　从问题的某一初始解出发；　

　while 能朝给定总目标前进一步 do　

　求出可行解的一个解元素；　　

由所有解元素组合成问题的一个可行解。

贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。
贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
      对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2.最优子结构性质
       当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
贪心法的一般流程

代码如下:

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;

问题描述：

当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）

问题分析：

根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。

问题的算法设计与实现：

先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。

代码如下:

//找零钱算法
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案
 public static int[] zhaoqian(int m[],int n)
 {
        int k=m.length;
        int[] num=new int[k];
        for(int i=0;i<k;i++)
        {
                num<i>=n/m<i>;
                n=n%m<i>;
        }
        return num;
 }

代码如下:

public class zhaoqian
{
 public static void main(String[] args)
 {
        int m[]={25,10,5,1};
        int n=99;
        int[] num=new int[m.length];
        num=zhaoqian(m,n);
        System.out.println(n+"的找钱方案：");
        for(int i=0;i<m.length;i++)
        System.out.println(num<i>+"枚"+m<i>+"面值");
 }
 public static int[] zhaoqian(int m[],int n)
 {
        int k=m.length;
        int[] num=new int[k];
        for(int i=0;i<k;i++)
        {
                num<i>=n/m<i>;
                n=n%m<i>;
        }
        return num;
 }
}

以上所述就是本文的所有内容了，希望小伙伴们能够喜欢。

赞 (0)

相关推荐

  • Java贪心算法之Prime算法原理与实现方法详解

    Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

  • java字符串相似度算法

    本文实例讲述了java字符串相似度算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class Levenshtein {     private int compare(String str, String target) {         int d[][]; // 矩阵         int n = str.length();         int m = target.length();         int i; // 遍历str的      

  • 图解程序员必须掌握的Java常用8大排序算法

    图解程序员必须掌握的Java常用8大排序算法

    这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序,分享给大家一起学习. 分类 1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不稳定:快速排序,希尔排序,堆排序. 先来看看8种排序之间的关系: 1.直接插入排序 (1)基本思想

  • 基于Java实现的Dijkstra算法示例

    本文以实例形式介绍了基于Java实现的Dijkstra算法,相信对于读者研究学习数据结构域算法有一定的帮助. Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法.即先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止. 其代码实现如下所示: package com.algorithm.impl; public class Dijkstra { private static int M =

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • java冒泡排序算法代码

    复制代码 代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 *  * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) {        for (int i = 0; i < n; i++) {            int flag = 0; 

  • 使用java自带des加密算法实现文件加密和字符串加密

    复制代码 代码如下: import java.io.ByteArrayInputStream;import java.io.ByteArrayOutputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.InputStream;import java.io.OutputStream;import java.security.SecureR

  • 分享Java常用几种加密算法(四种)

    对称加密算法是应用较早的加密算法,技术成熟.在对称加密算法中,数据发信方将明文(原始数据)和加密密钥(mi yue)一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去.收信方收到密文后,若想解读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文.在对称加密算法中,使用的密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密,这就要求解密方事先必须知道加密密钥. 简单的java加密算法有: BASE 严格地说,属于编码格式,而非加密算法 MD(Mes

  • java实现MD5加密算法的实例代码

    复制代码 代码如下: package other; import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;/* * MD5 算法*/public class MD5 { // 全局数组    private final static String[] strDigits = { "0", "1", "2", "3", &

随机推荐