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; 
      } 
     } 
    }