淺析java貪婪算法。本站提示廣大學習愛好者：（淺析java貪婪算法）文章只能為提供參考，不一定能成為您想要的結果。以下是淺析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;
}
}
以上所述就是本文的一切內容了，願望小同伴們可以或許愛好。
