AV3 Tehniki na Algoritmi Zadaca 3

public class Zadaca3 {
    //KODOT E SO NEKOI GRESKI
    public static void main(String[] args) {
        int[] moneti=new int[5];

        System.out.println(brojNaMoneti_verzija1(13));
        System.out.println(brojNaMoneti_verzija2(13, new int[]{1,2,5,10,50},5,moneti));
    }

    static int brojNaMoneti_verzija1(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;
        int []moneti={50,10,5,2,1};
        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;
    }

    static int brojNaMoneti_verzija2(int suma, int[] paricki, int n, int[]moneti)
    {
        //resenie so alcen agloritam
        sortirajParicki(paricki , n);
        //paricki = 50 10 5 2 1
        int i=0;
        int brojacZaMoneti=0;


        while(suma>0)
        {
            //se dodeka suma>0 i odzemam od parickite
            moneti[i]=suma/paricki[i];
            //ja zimame sumata i delime so brojot na paricki
            //ako sumata ni e 150 i imame 10 paricki br na moneti e 15

            suma-=moneti[i] * paricki[i];
            brojacZaMoneti=brojacZaMoneti + moneti[i];
            i++;
        }

        while(i<n)
        {
            paricki[i]=0;
            i++;
        }
        return brojacZaMoneti;

    }

    static void sortirajParicki(int paricki[] , int n , int[]moneti)
    {
        //sakame da gi sortirame parickite za potoa polesno da mozeme da pristapime do niv
        //paricki[] n -brojot na pari
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
                //j=i+1 oti sporeduvame sekoe so sekoe
            if(paricki[i]<paricki[j])
            {
                //gi mestime vo opagacki redosled
                int temp=paricki[i];
                paricki[i]=paricki[j];
                paricki[j]=temp;
            }
        }
    }
}