演算法題找零錢

A. c語言 找零錢問題，謝謝

這很容易。
先輸入n值，然後從最大面值的人民幣開始減。例如：
我有238元
減最大面值的第一個。238－100＝138。結果為正數且不為零。然後記錄100元張數的變數加1（這些變數都應初始化時為0）
繼續，138－100＝38.結果正數且不為零，同上100面值變數加1，
38－100。結果小於零。不再用100面值的減。
38－50。結果同樣小於零，不再用50面值的減。
38－20＝18.結果為正數且不為零，20元張數的變數加1，
18－20。結果小於零。不再用20面值的減。
18－10＝8。結果為正數且不為零，10元張數的變數加1，
8－10.結果小於零。不再用10面值的減。
8-5＝3。結果為正數且不為零，5元張數的變數加1，
3-5。結果小於零。不再用5面值的減。
3-2＝1.結果為正數且不為零，2元張數的變數加1，
1-1＝0.結果為零。1元張數變數加1.顯示結果。

你有：
100元（2）張，50元（0）張，20元（1）張，10元（1）張，5元（1）張，2元（1）張，1元（1）張。

B. 程序員演算法基礎——貪心演算法

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

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

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

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

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用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]的值。

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

C. 鎵鵑浂閽辯畻娉曢棶棰

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

D. 請問數錢的貪婪演算法怎樣確保得到最優解

貪婪演算法：總是作出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解。
（註：貪婪演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。

基本思路：——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

基本要素：
1、 貪婪選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇，即貪婪選擇來達到。（與動態規劃的主要區別）
採用自頂向下，以迭代的方式作出相繼的貪婪選擇，每作一次貪婪選擇就將所求問題簡化為一個規模更小的子問題。
對於一個具體問題，要確定它是否具有貪婪選擇的性質，我們必須證明每一步所作的貪婪選擇最終導致問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪婪選擇開始的，而且作了貪婪選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步作貪婪選擇，最終可得到問題的一個整體最優解。
2、最優子結構性質:包含子問題的最優解
1、 設有n個活動的安排，其中每個活動都要求使用同一資源，如演講會場，而在同一時間只允許一個活動使用這一資源。每個活動都有使用的起始時間和結束時間。問：如何安排可以使這間會場的使用率最高。
活動 起始時間 結束時間
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14

演算法：一開始選擇活動1，然後依次檢查活動一i是否與當前已選擇的所有活動相容，若相容則活動加入到已選擇的活動集合中，否則不選擇活動i,而繼續檢查下一活動的相容性。即：活動i的開始時間不早於最近加入的活動j的結束時間。
Prodere plan;
Begin
n:=length[e];
a {1};
j:=1;
for i:=2 to n do
if s[i]>=f[j] then
begin a a∪{i};
j:=i;
end
end;

例1 [找零錢] 一個小孩買了價值少於1美元的糖，並將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所採用的貪婪准則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等於要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。

假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然後是5美分的，最後加入兩個1美分的硬幣。

貪婪演算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明採用上述貪婪演算法找零錢時所用的硬幣數目的確最少（見練習1）。

E. 【演算法 - 動態規劃】找零錢問題Ⅱ

動態規劃新解：深度探索找零錢問題Ⅱ

在動態規劃系列的璀璨篇章中，我們已經領略了四種經典模型的魅力：從左到右的精妙、范圍嘗試的巧妙、樣本對應的智慧和業務限制的實用性。今天，我們將聚焦於更具挑戰性的找零錢問題Ⅱ，給定正整數貨幣數組arr和目標金額aim，目標是計算組合方式的總數，但與問題Ⅰ不同，這里限制了每種貨幣的張數。

想像一下，當你面對arr={1,2,1,2,1,2,1}，aim=4的場景，需要多少種獨特的組合方式，其中每種貨幣張數有限制。暴力遞歸的思路是關鍵，但這里我們將引入動態規劃的力量，以記憶化搜索和狀態轉移方程為武器，降低枚舉的復雜性。

暴力遞歸到動態規劃的蛻變

暴力遞歸的基礎在於：當遍歷到數組末尾，且剩餘金額為零時，我們找到了一個有效組合，計數加一。但這里的關鍵在於處理張數限制，即zhang不能超過coins[index]的值。將遞歸轉換為動態規劃，我們構建一個二維數組dp，大小為[N+1][aim+1]，初始化dp[N][0]=1，從後向前填充，利用dp[i+1][rest]計算dp[i][rest]，從而消減一層循環。

在優化版本中，我們觀察到一個有趣的規律：計算dp[i][rest]時，可以通過枚舉zhang，並利用dp[i+1][rest-coins[index]*zhang]來代替冗餘的循環，這就像將紅色計算簡化為淡黃色、藍色和橙色的組合，降低了復雜度，同時避免了處理藍色貨幣選擇時的邊界問題。

動態規劃的魅力與應用

動態規劃的精髓在於表依賴和記憶化，它巧妙地將復雜問題轉化為子問題的組合。在這個找零錢問題中，通過嚴格遵守狀態轉移方程，我們不僅消除了多餘的for循環，還提升了代碼的效率和可讀性。掌握動態規劃的這些技巧，就如同為演算法大廈奠定堅固的基礎，回顧過去的篇章，你將發現每一個模型都在為解決新問題提供關鍵的線索。

總結來說，動態規劃的魔力在於其簡潔的邏輯和高效的執行。通過深入理解記憶化搜索和狀態轉移，我們在找零錢問題Ⅱ中實現了從暴力遞歸到優雅動態規劃的轉變，這不僅降低了計算的復雜度，也提升了問題解決的美感。讓我們繼續在動態規劃的海洋中探索，深化理解，迎接更多演算法挑戰。