貪心演算法找零錢

⑴ 找零錢問題的貪心演算法

問題描述：
當前有面值分別為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分。
具體實現
//找零錢演算法
//By falcon
//輸入：數組m，依次存放從大到小排列的面值數，n為需要找的錢數，單位全部為分
//輸出：數組num，對照數組m中的面值存放不同面值的硬幣的個數，即找錢方案

⑵ 程序員演算法基礎——貪心演算法

貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。

比如一道常見的演算法筆試題---- 跳一跳 ：

我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。

狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選纖啟擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。

貪毀局如心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的臘山問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？

假如我們把題目變成這樣，原來的策略還能生效嗎？

接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。

對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）

如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：

我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。

這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。

如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。

我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；

這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。

先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）

如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。

⑶ 求背包問題貪心演算法實例結果

找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少
背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．可用P/W來解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的結構體
{
double p;//價值
double w;//重量
double r;//價值與重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品個數
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//調用sort排序函數，你大概不介意吧，按照價值與重量比排序貪心
scanf("%lf",&m);//讀入包的容量m
s=0;//包內現存貨品的重量
value=0;//包內現存貨品總價值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//輸出結果
return 0;
}

⑷ 鎵鵑浂閽辯畻娉曢棶棰

鏈鍏堢敤1涓25鍒嗭紝鐒跺悗閫掑綊奼傚墿浣 50-25=25 鑳戒笉鑳界敤 5涓10鍒嗭紝0涓5鍒嗭紝4涓1鍒 鎵鵑浂錛屽傛灉鑳斤紝鍒欒繑鍥炵粨鏋滐紝濡傛灉涓嶈兘鍒欑敤0涓25錛岀劧鍚庨掑綊奼傚墿浣 50-0=50 鑳戒笉鑳界敤 5涓10鍒嗭紝0涓5鍒嗭紝4涓1鍒 鎵鵑浂銆

⑸ 貪心思想

在學習數據結構的時候，我們已經見過了貪心思想在Prim和Kruskal中的完美應用，貪心思想因為其的簡潔在演算法中經常會被用到，有的時候在生活中，我們也會無意中使用到l貪心演算法。比如在去shopping時，經常需要進行找零錢的過程，我們總是不自覺的先把大的找出來。

那麼什麼是貪心思想？

貪心演算法總是作出在當前看來最好的選擇，也就是說貪心演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

只有在滿足最優子結構的情況下貪心演算法得到的結果才是最優結果。

比如找錢的問題，我要給你一百，那麼我盡可能每一次給你最多的。

或者比如磁碟的最優存儲問題，所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。

Prim和kruskal演算法都是每次選擇最小的邊納入生成樹。

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這也是貪心問題和動態規劃問題的主要區別。

在n行m列的正整數矩陣中，要求從每一行中選一個數，使得選出的n個數的和最大。

可運用貪心策略，選n次，每一次選相應行中的最大值即可。

但是，在一個n*m的方格陣中，每一格子賦予一個數，規定每次移動時只能向上或向右，現試找出一條路徑，使其從左下角至右上角所經過的權值之和最大。

同樣考慮貪心策略，從左下角向右上角移動，每次移動選擇權值較大的一個方向。

以2*3矩陣為例，採用貪心的策略得到的是1,3,4,6和為14但是實際的最優結果為1,2,100,6和為109.

所以說貪心演算法並不是總是可行，證明當前問題存在貪心選擇性質（全局最優解可以通過局部最優貪心選擇達到）和最優子結構性質（問題的最優解包含了其子問題的最優解）。所以貪心問題如果當前的選擇不會干擾之後的選擇，則不會出現問題。

其他的情況就需要進行證明，證明的最好辦法就是將最小子問題進行一步步的合並，直到最後還原為最後的原問題，若所得到的解是總體最優的則可以使用貪心思想，否則不可以。

比如上面的問題，我們的走一步的最優解為1，3，然後我們判斷一次走兩步的最優解是否任然為1,3這個路徑，答案顯然不是，變為 1,2,100這個路徑，所以顯然不能使用貪心思想。

假設1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現在要用這些錢來支付K元，至少要用多少張紙幣？用貪心演算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。

有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。

部分背包問題， 有n個物體，第i個物體重量為wi,價值為vi,在總重量不超過C的情況下，讓總價值盡可能的高。每個物體都可以只取一部分。

我們可以考慮重量和價值的比值作為單價。

⑹ 找零錢問題 [貪心演算法](java實現）

public getMin{

public int MinNumber=0;

public int findMax(int[] a){
for(int i=0;i<a.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}

public boolean Compare(int a,int b){
public boolean flag=true;
if(a>b) flag=flase;
return flag;
}

public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];

int index=0;

for(int i=0;i<M.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}

int max = this.findMax(findM);
MinNumber++;

if((Money-max)!=0) {
getMinNumber(M,Money-max)
}

return MinNumber;
}

public int[] Start(){
System.out.println("請輸入查詢組數");
int group=System.in.read();

int[] M={1,2,5,10,20,50,100};

int[] Result = new Int[group];
int index=0;

while (group-- > 0){
System.out.println("請輸入金額");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}

public void print(int[] MinNumber){
for(int i=0;i<MinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}

public static void main(String[] args){
new getMin().print(new getMin().Start());
}

沒測試啊，有問題請勿噴，呵呵