淺析java貪心算法

2019-11-26 15:18:34

字體：大中小

來源：轉載

供稿：網友

貪心算法的基本思路

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;
 }
}