商品を購入する際、やり取りするお金の最小の枚数を求める | Codetter（こーどったー）

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)+ "枚");
		}
	}
}