儘量減少換手的硬幣數量

您有一套硬幣5¢，10¢，20¢，50¢，1 $，2 $和每個面額的數量有限。當您支付一定金額時，有兩種可能性：您支付正確的金額，或者您支付比所需更多的費用，並從店員那裏收到正確的更改。如何最小化改變手牌的硬幣數量（即最大限度地減少您輸入的硬幣數量加上您收到的硬幣數量）。假設金額始終是可支付的，而店員有無限數量的金幣，並且他總是選擇最有效的方式來回復變更。儘量減少換手的硬幣數量

我認爲，爲了儘量減少轉手的數量，你必須儘量減少你給的硬幣數量和你收到的硬幣數量。收到的硬幣數量可以使用通常的硬幣更換算法來最小化，但是我不知道如何最小化一組固定硬幣的變化。

對於全問題的說明：UVA Online Judge

來源

2013-03-06 Minh Pham

這是一個有趣的練習，但是你有什麼問題？你有什麼嘗試？你卡在哪裏？你的代碼在哪裏？ – John 2013-03-06 16:16:14

謝謝，我編輯了我的描述。 – 2013-03-06 16:23:24

對於這個特定的硬幣組，貪婪算法的作品（試圖證明這一點）。一般來說，它更復雜。 – us2012 2013-03-06 16:26:48

最小化的硬幣數量那筆給定量是Knapsack Problem的一個版本。

你的問題是要儘量減少coins(S1) + coins(S2)（你是店員+店員），其中S1 - S2 = S（你應該支付的金額）。所以，你要解決揹包問題的S和Smax之間變化的所有值（知道coins(x)所有值），然後解決：

min coins(S1) + coins(S2) 
under constraints 
    S1 - S2 = S 
    S1 in [S, Smax]

這可以通過簡單枚舉（測試每個可能值來解決S1）。

現在的問題是確定Smax的值。

我不知道這，但我認爲，因爲你最大的硬幣是$ 2，如果你給店員的東西大於S + 2 $，你不會有任何少硬幣轉移。所以我的猜測是Smax = S + 2$，但我邀請你多給一點思考。

來源

2013-03-06 16:23:20 alestanis

使用你的符號：如果S1> S + 2，那麼店員會給你一個2美元的硬幣，因爲他的最佳選擇是貪婪算法，因爲這套硬幣。因此，有一個更好的解決方案，不是把這個2美元的硬幣交給店員。警告：這對於任何一組硬幣都不適用。例如：如果你有5美元和7美元的硬幣，你想支付16美元。在這種情況下，Smax = S + maxcoin = 16 + 5 = 21，但是S1> 21.S1 = 30（6×5美元），S2 = 14（2×7美元）。 – 2013-03-06 18:29:05

我最近在my blog解決了這個問題。這裏的結局，但你必須閱讀整個博客條目這是有道理的：

(define (floupia price coins) 
    (if (positive? (modulo price (apply gcd coins))) 
     (error 'floupia "infeasible") 
     (let ((coins (append coins (map negate coins)))) 
     (let loop ((n 1)) 
      (let ((xs (filter (lambda (xs) (= (sum xs) price)) 
          (combinations-with-replacement n coins)))) 
      (if (null? xs) (loop (+ n 1)) xs))))))

的基本思路是，首先看一個硬幣可以支付賬單，然後兩個硬幣，然後是三個，等等，當你找到最小的解決方案時停止。在每個步驟考慮所有硬幣的所有可能的組合，以及替換，以查看是否存在解決方案，將收到的變化視爲負值硬幣。例如，面額1,3,7,31和153的硬幣以及目標價格爲17的硬幣有5個硬幣的解決方案，其中包括支付3個7個硬幣並收回單個1個硬幣和3個硬幣但是更有效的解決方案是支付31個硬幣並且更換兩個7個硬幣。

來源

2013-03-06 18:27:59 user448810

我不確定你的意思是：當你找到最小的解決方案時停止。如果你有2枚硬幣：1枚和100枚，而你想支付5枚。有一個解決方法是給一枚100枚硬幣，然後得到95枚1枚硬幣。但最好還是給5個。最好的解決方案並不一定是你減少硬幣的方案。 – 2013-03-06 18:34:55

上面循環中的硬幣數量n從1開始，並在循環中的每一步都增加。在你的例子中，n從1開始，沒有可行的解決方案，所以n增加到2，沒有可行的解決方案，等等，直到n達到5並且找到支付5個1個硬幣的解決方案，當你停止時。在每一步都會生成所有可能的硬幣組合，並進行替換，然後對每個硬幣進行彙總，以確定它是否爲目標。有關完整說明，請參閱上面的博客條目參考。 – user448810 2013-03-06 23:34:28

我不同意。對於n = 1，有一個解決方案：你給100個硬幣。 – 2013-03-07 17:21:57

這是一個NP完全問題的類型，它通常使用啓發式搜索來解決。相關的啓發式是首先嚐試更大的面值。

來源

2013-03-06 20:05:34

儘量減少換手的硬幣數量

回答

相關問題