商品を購入する際、やり取りするお金の最小の枚数を求める

(やり取りする金額と、その世界で何円コインがあるかの配列)を渡すと、やり取りする最小枚数を返してくれます。

(やり取りする金額と、その世界で何円コインがあるかの配列)を渡すと、やり取りする最小枚数を返してくれます。

  • タグ:
  • タグはありません
import java.util.Arrays;
import java.util.Random;
public class Main {
public static int turi(int p1, int[] coins) {
int len = coins.length;
int[] coin = new int[len];
System.arraycopy(coins, 0, coin, 0, len);
Arrays.sort(coin);
return _turi(Math.abs(p1) % coin[len - 1], Math.abs(p1) / coin[len - 1], len - 2, coin, 0);
}
private static int _turi(int p1, int mai, int en, int[] coin, int flag) {
if(en < 0) return p1 == 0 ? mai: 999999999;
int a = _turi(p1 % coin[en], mai + p1 / coin[en], en - 1, coin, 0);
if(flag == 1) return a;
int b = _turi(coin[en + 1] - p1, mai + 1, en, coin, 1);
return a < b ? a : b;
}
/////////////////////////////////////////////////////////////////////////////
public static void main(String[] args) {
int[] coins = {1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000};
Random r = new Random();
for (int i = 0; i < 1000; i++) {
int kingaku = r.nextInt(100000);
System.out.println(""+kingaku+" = "+turi(kingaku, coins)+ "");
}
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX