Rapasoft.eu

public class Druha {
	
	public static int[] bankovky = {1,4,8,10,15}; //hodnoty bankoviek
	
	public static int[] pocetVypoctov = new int[2000];
	public static int[] stareVysledky = new int[2000];
	
	public static int minVyplatenie(int suma){
		if (suma <0)
			return -1;
				
		if (stareVysledky[suma] !=-2)
			return stareVysledky[suma];
		
		if (suma==0)
			return 0;
				
		int result=Integer.MAX_VALUE;
		for(int i=0;i<bankovky.length;i++){
			int pom = minVyplatenie(suma-bankovky[i]);
			if (pom >= 0){
				if (result > pom+1)
					result = pom + 1;
			}
		}
		
		if(result == Integer.MAX_VALUE)
			stareVysledky[suma] = -1;
		else
			stareVysledky[suma] = result;
		
		return stareVysledky[suma];
	}
	public static void main(String[] args) {
		for (int i=0; i<stareVysledky.length;i++){
			stareVysledky[i] = -2;
		}
		System.out.println(minVyplatenie(1000)); // suma na vyplatenie
	}
}