コイン/紙幣の最低額を変更する方法は？

Question

これは簡単かもしれませんが、私はそれの周りに私の頭を得ることはできません。 私は自動販売機を作ろうとしていますが、これまでは非常に簡単でしたが、ユーザーに交換を与えるにはどうすればいいですか？この問題は、ユーザーが製品の価格よりも多くの金を払うと発生します。コークスが$ 2で、ユーザーが$ 4を支払うと、自動販売機は$ 2または$ 1の請求書を返すべきです。

Answer 1

この方法では、各ソリューションを調べて、最良のものを返します。 value配列は、各コイン/紙幣の値が昇順になります。可用性は、ディストリビュータで利用可能なその値のコイン/請求書の数です。

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

基準は、コイン/法案の少なくとも数であれば、isBestメソッドは次のようになります。時間のほとんどは、最初のソリューションも最高であることを

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

は注意。解決策が見つかった後も継続することは価値がないかもしれません。