Min-Coin變更 - 限量套裝的最佳解決方案

Question

前段時間我正在閱讀有關最小硬幣變更問題的內容，我想將其應用於假想的自動機器。

然而，一個自動機僅需要硬幣受限訪問，這將是良好的，返回到限制小型電動機，其提供每個硬幣的需要所需的硬幣的最小量。

貪心算法不能在這裏使用了我們想要的最佳解決方案，也爲機器的工作需要知道需要什麼每種類型的硬幣和多少。另一個事實是，有時機器沒有足夠的硬幣來提供所需的改變，並且一旦檢測到它就應該點亮小LED。

這是我在這裏看到計算器的問題不同，有的用醜陋的貪婪方法和別人不考慮採取實際情況，硬幣的數量有限。這更適用於真實世界問題。

如果我錯了，我會刪除的問題，只是想有可能在未來幾年真正的問題可以使用一些良好，穩定和明確的方向。

這是我的第一個問題，我希望它可以幫助未來的人。

Answer 1

我不知道ATM的電機限制，所以我只能看到一個問題 - 沒有足夠的硬幣所需的價值。

protected void CalculateCoins(int sum) 
    { 
     int remainder = sum; 
     int required = 0; 

     // Array of coins should be sorted by value of coins 
     CoinQnt[] normalizedCoins = new CoinQnt[] 
     { 
      new CoinQnt { Value = 50, Qnt = 1 } 
      , new CoinQnt { Value = 20, Qnt = 100 } 
      , new CoinQnt { Value = 10, Qnt = 100 } 
      , new CoinQnt { Value = 5, Qnt = 100 } 
      , new CoinQnt { Value = 2, Qnt = 100 } 
      , new CoinQnt { Value = 1, Qnt = 100 } 
     }; 

     Debug("Splitting {0}", sum); 
     // Loop through available coins 
     foreach(CoinQnt c in normalizedCoins) 
     { 
      if(remainder >= c.Value) 
      { 
       // Determine how many coins we need and how many are left 
       required = Math.Min(remainder/c.Value, c.Qnt); 
       Debug("Using {0} qnt of {1}", required, c.Value); 
       remainder -= required * c.Value; 
      } 
     } 
    }