AV3 Tehniki na Algoritmi Zadaca 3

Дадени се парички со одредена вредност (постојат парички од 50, 10, 5, 2 и 1 денар), и притоа бројот на парички од секоја вредност е
неограничен. За дадена сума да се определи најмалиот број на парички кои се потребни да се формира таа сума.
public class Zadaca3 {
    public static void main(String[] args) {

    }

    static int brojNaMoneti(int suma)
    {
        //50,10,5,2,1
        /*
        pr ako sumata ni e 150
        150/50=3 -> imame 3 50ki na raspolaganje
        150/10=15-> 10 50ki na raspolaganje
        150/5=30 -> 30 50ki na raspolaganje
        150/2=75 -> 75 2ki na raspolaganje
        150/1=150 -> 150 kecovi na raspolaganje
         */
        int rez=100000000;
        for(int m1=0;m1<=(suma/50);m1++)
        {
            for(int m2=0;m2<=(suma/10);m2++)
            {
                for(int m3=0;m3<=(suma/5);m3++)
                {
                    for(int m4=0;m4<=(suma/2);m4++)
                    {
                        for(int m5=0;m5<=suma;m5++)
                        {
                            int pom=m1*50 + m2*10 + m3*5 + m4*2 + m5*1;

                            if(pom==suma)
                            {
                                int brojNaParicki=m1+m2+m3+m4+m5;
                                if(rez>brojNaParicki)
                                {
                                    rez=brojNaParicki;
                                }
                            }

                        }
                    }
                }
            }
        }
        return rez;
    }
}