Zdrojový kód z prednášky 3.4.2012

public class Banka {

        // Nominalne hodnoty jednotlivych typov CP
        private int[] hodnotyCP;
        // Pole, do ktoreho generujeme pocetnosti jednotlivych typov CP v uvazovanom vyplateni
        private int[] poctyCP;

        // Najoptimalnejsi pocet cennych papierov, ktory sme doposial nasli
        private int najPocetCP;
        // Sucet pocetnosti CP vo vytvaranom rozdeleni
        private int pocetCP;

        private void spracuj() {
                if (pocetCP < najPocetCP) {
                        najPocetCP = pocetCP;
                }
        }

        private void generuj(int odIdx, int zostatok) {
                if (odIdx == hodnotyCP.length) {
                        if (zostatok == 0)
                                spracuj();

                        return;
                }

                for (int i = 0; i <= zostatok / hodnotyCP[odIdx]; i++) {
                        poctyCP[odIdx] = i;
                        pocetCP += i;
                        //if (pocetCP <= najPocetCP) {
                                generuj(odIdx + 1, zostatok - poctyCP[odIdx] * hodnotyCP[odIdx]);
                        //}
                        pocetCP -= i;
                        poctyCP[odIdx] = 0;
                }
        }

        public int minVyplatenie(int suma) {
                poctyCP = new int[hodnotyCP.length];
                najPocetCP = Integer.MAX_VALUE;
                generuj(0, suma);
                if (najPocetCP == Integer.MAX_VALUE)
                        return -1;
                else
                        return najPocetCP;
        }

        public Banka(int[] hodnotyCP) {
                this.hodnotyCP = hodnotyCP.clone();
        }

        public static void main(String[] args) {
                Banka statnaPokladnica = new Banka(new int[] { 100, 500, 800, 900, 50, 20, 5 });
                System.out.println(statnaPokladnica.minVyplatenie(10000));
        }
}

public class Banka {

        // Nominalne hodnoty jednotlivych druhov CP
        private int[] hodnotyCP;
        // Pole, do ktoreho si budeme zapamatavat uz vypocitane riesenia
        // podproblemov
        private int[] cache;

        /**
         * Metoda, ktora vrati minimalny pocet CP pre zadanu sumu s pouzitim
         * memoizacie
         */
        private int minPocetCP(int suma) {
                // Zaporne cislo - nie je co riesit...
                if (suma < 0)
                        return -1;

                // Ak sme uz optimalne vyplatenie sumy suma pocitali, vratime rovno to,
                // co mame v poli cache
                if (cache[suma] != Integer.MIN_VALUE) {
                        return cache[suma];
                }

                // Ak je suma 0, optimalny pocet je 0 - trivialny pripad
                if (suma == 0)
                        return 0;

                // Najdeme minimalny pocet CP tak, ze vyberieme taky typ CP, po ktoreho
                // odratani dostaneme sumu, ktoru mozno vyplatit s najmensim poctom
                // papierov.
                int minimum = Integer.MAX_VALUE;
                for (int i = 0; i < hodnotyCP.length; i++) {
                        int pom = minPocetCP(suma - hodnotyCP[i]);
                        // Specialne riesime, ked nam volanie vratilo -1. To hovori, ze sumu
                        // (suma - hodnotyCP[i]) nemozno vobec vyplatit. Pri hladani minima
                        // uvazujeme len sumy, ktore vyplatit mozno.
                        if (pom != -1) {
                                if (pom < minimum) {
                                        minimum = pom;
                                }
                        }
                }

                // Finalny vysledok je -1 (ak ziadnu z "mensich" nemozno vyplatit) alebo
                // 1+min (na zaklade rekurzivneho vzorceka)
                int vysledok;
                if (minimum == Integer.MAX_VALUE)
                        vysledok = -1;
                else
                        vysledok = 1 + minimum;

                // Pred vratenim vysledku, vysledok ulozime do cache
                cache[suma] = vysledok;
                return vysledok;
        }

        /**
         * Vrati minimalny pocet CP s pouzitim memoizacie
         */
        public int minVyplatenie(int suma) {
                cache = new int[suma + 1];
                minPocetCP(suma);
                return cache[suma];
        }

        /**
         * Riesenie ulohy dynamickym programovanim, kedy si obsah pola cache
         * systematicky vypocitame.
         */
        public int minVyplatenieDynamicky(int suma) {
                // Trivialny pripad
                cache[0] = 0;

                // Postupne vyplname policka pola cache od 1 po suma...
                for (int s = 1; s < cache.length; s++) {
                        // Odsimulujeme spravanie rekurzivnej implementacie s memoizaciou
                        int minimum = Integer.MAX_VALUE;
                        for (int i = 0; i < hodnotyCP.length; i++) {
                                int pom;
                                // Nahrada: int pom = minPocetCP(suma - hodnotyCP[i]);
                                if (s - hodnotyCP[i] >= 0) {
                                        // Namiesto rekurzivneho volania hodnotu rovno vytiahneme z
                                        // cache
                                        pom = cache[s - hodnotyCP[i]];
                                } else {
                                        pom = -1;
                                }

                                if (pom != -1) {
                                        if (pom < minimum) {
                                                minimum = pom;
                                        }
                                }
                        }

                        int vysledok;
                        if (minimum == Integer.MAX_VALUE)
                                vysledok = -1;
                        else
                                vysledok = 1 + minimum;

                        // Namiesto vratenia hodnoty len
                        cache[s] = vysledok;
                }

                return cache[suma];
        }

        public Banka(int[] hodnotyCP) {
                this.hodnotyCP = hodnotyCP.clone();
        }

        public static void main(String[] args) {
                Banka statnaPokladnica = new Banka(new int[] { 100, 500, 800, 20, 50,
                                30, 10, 5, 25, 1, 2, 3, 10 });
                System.out.println(statnaPokladnica.minVyplatenieDynamicky(10000000));
        }
}