硬幣找零問題

• 前言
  • 所謂貪心算法，就是遵循某種既定原則，不斷選取當前條件下最優的選擇來構造每一個子步驟的解決方案，直到獲得問題最終的求解。即在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，所做的僅是在某種意義上的局部最優解。
  • 利用貪心算法，需要解決兩個問題。
    • 一是問題是否適合使用貪心算法求解，即所求解問題是否具有貪心選擇性質。所謂貪心選擇性質，是指應用同一規則f，將原問題變為一個相似的但規模更小的子問題，后面的每一步都是當前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局上看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。
    • 二是問題是否具有局部最優解，從而通過一個貪心標準，可以得到問題的最優解。
  • 利用貪心算法解題的思路一般為：
    • 建立對問題精確描述的數學模型，包括定義最優解的模型。
    • 將問題分解為一系列子問題，同時定義子問題的最優解結構。
    • 應用貪心算法原則可以確定每個子問題的局部最優解，并根據最優解模型，用子問題的局部最優解堆疊出全局最優解。
• 問題描述
  • 對于給出的商店擁有的各種硬幣的面值及其數目以及付款金額，如何計算使用最少硬幣的方案？
• 問題分析
  • 核心思想為消費者硬幣數量有限，商店的硬幣無限。因此，問題可以用如下公式描述：
    • min(消費者支付硬幣數量+商店找零硬幣數量)
    • 支付值-找零值=商品值
  • 可以理解為問題的求解就是上面兩個問題的最優解。
  • 這里使用的貪心算法為max(消費者擁有的硬幣面值-商店擁有的硬幣面值)優先使用。
    • 例如消費者擁有面值2元的硬幣，商店擁有5分的硬幣，因此max=200-5=195。上面的組合情況為200,200-5,200-10,…,5。
    • 現在加入購買的商品是2元的，那么上面的組合中使用2元優先，只用一個硬幣即可。假如商品是2元9角5分，上面的序列存在“100-5”的情況，這是能夠使用的最大幣值（貪心），就用它了，那么它是2枚硬幣，即支付1元找零5分，共用了三枚硬幣。
  • 驗證算法的貪心選擇性和最優子結構性質即可證明貪心算法可以得到最優解。
• 代碼
  • # -*-coding:utf-8-*-d = [0.05, 0.1, 0.2, 0.5, 1, 2]d_sum = [2, 3, 4, 5, 6, 4]sum_value = 0for i in range(len(d)):sum_value += d_sum[i] * d[i]input_value = 2.5if input_value > sum_value:print("cannot change")else:i = 5while i >= 0:if input_value >= d[i]:n = int(input_value/d[i])if n >= d_sum[i]:n = d_sum[i]input_value -= n * d[i]print("使用了{}個{:.2f}".format(n, d[i]))i -= 1
• 運行結果
• 補充說明
  • 具體代碼可以查看我的Github，歡迎Star或者Fork
  • 參考書《你也能看得懂的Python算法書》

總結

以上是生活随笔為你收集整理的贪心算法-01硬币找零问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。