淺析java貪心算法

更新時(shí)間：2015年02月02日 10:02:01 投稿：hebedich

這篇文章簡單主要介紹了java貪心算法，包含貪心算法的基本思路，性質(zhì)，以及實(shí)現(xiàn)示例，有需要的小伙伴參考下

貪心算法的基本思路

1.建立數(shù)學(xué)模型來描述問題?！?/p>

　2.把求解的問題分成若干個(gè)子問題?！?/p>

　3.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解?！?/p>

　4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解?！?/p>

　實(shí)現(xiàn)該算法的過程：　

　從問題的某一初始解出發(fā)；　

　while 能朝給定總目標(biāo)前進(jìn)一步 do　

　求出可行解的一個(gè)解元素；　　

由所有解元素組合成問題的一個(gè)可行解。

貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，換句話說，當(dāng)考慮做何種選擇的時(shí)候，我們只考慮對(duì)當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。這是貪心算法可行的第一個(gè)基本要素。
貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。
對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。

2.最優(yōu)子結(jié)構(gòu)性質(zhì)
當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。
貪心法的一般流程

復(fù)制代碼代碼如下:

Greedy(C)  //C是問題的輸入集合即候選集合

{

    S={ };  //初始解集合為空集

    while (not solution(S))  //集合S沒有構(gòu)成問題的一個(gè)解

    {

       x=select(C);    //在候選集合C中做貪心選擇

       if feasible(S, x)  //判斷集合S中加入x后的解是否可行

          S=S+{x};

          C=C-{x};

    }

   return S;

問題描述：

當(dāng)前有面值分別為2角5分，1角，5分，1分的硬幣，請(qǐng)給出找n分錢的最佳方案（要求找出的硬幣數(shù)目最少）

問題分析：

根據(jù)常識(shí)，我們到店里買東西找錢時(shí)，老板總是先給我們最大面值的，要是不夠再找面值小一點(diǎn)的，直到找滿為止。如果老板都給你找分?jǐn)?shù)的或者幾角的，那你肯定不干，另外，他也可能沒有那么多零碎的錢給你找。其實(shí)這就是一個(gè)典型的貪心選擇問題。

問題的算法設(shè)計(jì)與實(shí)現(xiàn)：

先舉個(gè)例子，假如老板要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數(shù)，為了找給我最少的硬幣數(shù)，那么他是不是該這樣找呢，先看看該找多少個(gè)25分的，誒99／25＝3，好像是3個(gè)，要是4個(gè)的話，我們還得再給老板一個(gè)1分的，我不干，那么老板只能給我3個(gè)25分的拉，由于還少給我24，所以還得給我2個(gè)10分的和4個(gè)1分。

復(fù)制代碼代碼如下:

//找零錢算法

//輸入：數(shù)組m，依次存放從大到小排列的面值數(shù)，n為需要找的錢數(shù)，單位全部為分

//輸出：數(shù)組num，對(duì)照數(shù)組m中的面值存放不同面值的硬幣的個(gè)數(shù)，就找錢方案

 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;

 }

復(fù)制代碼代碼如下:

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;

 }

}