如何改變最少數量的硬幣/賬單？

Question

這可能聽起來不那麼容易，但我無法理解它。 我想製作一臺自動售貨機，直到現在一直非常簡單，但我怎麼給用戶交換最少量的硬幣？問題出現在用戶比產品價格更多的錢上。如果可樂是2美元，用戶給4美元，自動售貨機應該支付2美元或2美元的費用

Answer 1

這種方法將檢查每個解決方案並返回最好的一個。值數組是按升序排列的每個硬幣/賬單的值。可用性是分銷商可用的硬幣/票據數量。

private static int[] bestChange(int amount, int[] value, 
      int[] availability) { 
     int[] change = new int[value.length]; 
     int[] best = null; 
     int i = value.length; 
     int m = amount; 
outer: 
     while (true) { 
      --i; 
      int v = value[i]; 
      int n = Math.min(m/v, availability[i]); 
      change[i] = n; 
      m -= n*v; 
      if (m == 0) { 
       System.out.println("Solution found: " 
         + toString(change, value)); 
       if (best == null || isBest(change, best)) { 
        System.out.println(" best so far"); 
        best = change.clone(); 
       } 
      } 
      if (i == 0 || m == 0) { 
       m += n*v; 
       change[0] = 0; 
       do { 
        ++i; 
        if (i == value.length) { 
         break outer; 
        } 
       } while (change[i] == 0); 
       --change[i]; 
       m += value[i]; 
      } 
     } 
     return best; 
    } 

如果標準是硬幣/紙幣的數量最少，最終的決定的方法是這樣的：

private static boolean isBest(int[] change, int[] best) { 
    return count(change) < count(best); 
} 

private static int count(int[] change) { 
    int n = 0; 
    for (int c: change) { 
     n += c; 
    } 
    return n; 
} 

注意，大部分的時間，第一個解決方案也是最好的;因此找到解決方案後可能不值得繼續。