Zdrojový kód k 7. prednáške

public class Banka {
        // Konstanta pouzita na oznacenie, ze sumu nejde vyplatit
        public static final int NEDA_SA = -1;

        // Nominalne hodnoty cennych papierov
        private int[] hodnotyCP;
        // Pole, v ktorom budeme generovat pocetnosti jednotlivych typov cennych
        // papierov,
        private int[] poctyCP;

        // Premenna, v ktorej si uchovavame sumu, ktoru nam ostava vyplatit
        private int suma;
        // Pocet cennych papierov, ktore pouzivame v aktualne generovanom vyplateni
        private int pocetCP;
        // Najlepsi (najmensi) pocet cennych papierov, ktory sme doposial nasli
        private int najPocetCP;

        /**
         * Ak je zostatkova suma presne 0 (vyskladali sme presne pozadovanu sumu),
         * overime, ci aktualne riesenie nie je lepsie ako doposial najlepsie.
         */
        private void spracuj() {
                if (suma != 0)
                        return;

                if (pocetCP < najPocetCP) {
                        najPocetCP = pocetCP;
                }
        }

        /**
         * Generujeme vsetky mozne vyplatenia sumy pocnuc zadanym indexom (typom
         * CP).
         *
         * @param odIdx
         */
        private void generuj(int odIdx) {
                if (odIdx == poctyCP.length) {
                        spracuj();
                        return;
                }

                for (int i = 0; i <= suma / hodnotyCP[odIdx]; i++) {
                        // Skusime generovat vsetky riesenia, v ktorych z CP na indexe odIdx
                        // pouzijeme presne i kusov
                        poctyCP[odIdx] = i;
                        suma -= i * hodnotyCP[odIdx];
                        pocetCP += i;

                        // Generujeme...
                        generuj(odIdx + 1);

                        // Po preskumani vygenerovanych rieseni obnovime povodny stav pola a
                        // premennych.
                        suma += i * hodnotyCP[odIdx];
                        pocetCP -= i;
                        poctyCP[odIdx] = 0;
                }
        }

        public int minVyplatenie(int suma) {
                this.suma = suma;
                pocetCP = 0;
                najPocetCP = Integer.MAX_VALUE;

                // Generujeme vsetky mozne vyplatenia
                generuj(0);

                // Ak sme nasli nejake vyplatenie (minimum uz nie je MAX_VALUE), vratime
                // pocet inak specialnu informaciu, ze sumu nejde vyplatit.
                if (najPocetCP != Integer.MAX_VALUE)
                        return najPocetCP;
                else
                        return NEDA_SA;
        }

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

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

import java.util.Arrays;

/**
 * Rekurzivne riesenie doplnene o memoizaciu (ukladanie si uz vypocitanych
 * hodnot)
 */
public class BankaMemoizacia {
        // Konstanta pouzita na oznacenie, ze sumu nejde vyplatit
        public static final int NEDA_SA = -1;
        // Konstanca indikujuca, ze optimalne vyplatenie pre zadanu sumu nebolo este
        // pocitane.
        public static final int NEBOLO_POCITANE = -2;

        // Nominalne hodnoty cennych papierov.
        private int[] hodnotyCP;
        // Pole, do ktoreho budeme uchovavat hodnoty uz vypocitanych optimalnych
        // vyplateni.
        private int[] cache;

        private int minVyplatenie(int suma) {
                if (suma < 0)
                        return NEDA_SA;

                // Ak uz sme minimalne vyplatenie pocitali, vratime hodnotu z "cache"
                // pola.
                if (cache[suma] != NEBOLO_POCITANE) {
                        return cache[suma];
                }

                // Ak sme tu, tak minimalne vyplatenie pre sumu suma este nebolo
                // pocitane. Aplikujeme teda vzorcek na vyratanie minimalneho vyplatenia
                // z minimalnych vyplateni niektorych mensich sum.

                if (suma == 0)
                        return 0;

                // Skusime zo sumy odobrat postupne kazdy typ CP a najst minimalne
                // vyplatenie pre zostavajucu sumu.
                int minPocet = Integer.MAX_VALUE;
                for (int i = 0; i < hodnotyCP.length; i++) {
                        int pom = minVyplatenie(suma - hodnotyCP[i]);
                        if (pom == NEDA_SA)
                                continue;

                        minPocet = Math.min(minPocet, pom);
                }

                // Definitivny vysledok ulozime do premennej (pokojne mozeme hodnotu
                // namiesto premennej vysledok rovno ulozit aj do cache[suma])
                int vysledok;
                if (minPocet == Integer.MAX_VALUE)
                        vysledok = NEDA_SA;
                else
                        vysledok = minPocet + 1;

                // Vyslednu hodnotu ulozime do cache pre pripad, ze by sme ju este
                // niekedy chceli pocitat.
                cache[suma] = vysledok;
                return vysledok;
        }

        public int minVyplatenieSCache(int suma) {
                // Vyrobime cache s indexami 0..suma
                cache = new int[suma + 1];
                // Poznacime si, ze sme ziadnu z hodnot este nepocitali
                Arrays.fill(cache, NEBOLO_POCITANE);
                // Zavolanim rekurzivneho vypoctu hladame najlepsie vyplatenie.
                return minVyplatenie(suma);
        }

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

        public static void main(String[] args) {
                BankaMemoizacia statnaPokladnica = new BankaMemoizacia(new int[] { 100,
                                500, 800 });
                System.out.println(statnaPokladnica.minVyplatenie(100000));
        }
}

/**
 * Riesenie zalozene na dynamickom programovani (namiesto memoizacie len
 * "vyplname" rovno cache)
 */
public class BankaDP {
        // Konstanta pouzita na oznacenie, ze sumu nejde vyplatit
        public static final int NEDA_SA = -1;
        // Konstanca indikujuca, ze optimalne vyplatenie pre zadanu sumu nebolo este
        // pocitane.
        public static final int NEBOLO_POCITANE = -2;

        // Nominalne hodnoty cennych papierov.
        private int[] hodnotyCP;

        /**
         * Najdeme optimalne vyplatenie aplikovanim dynamickeho programovania.
         */
        public int minVyplatenieDP(int suma) {
                // Vyrobime pole, ktore ideme vyplnat. cache[s] obsahuje minimalne
                // vyplatenie pre sumu s.
                int[] cache = new int[suma + 1];

                // Vyplnat cache NEBOLO_POCITANE netreba, kedze systematicky budeme
                // vyplnat kazde jedno policko
                // Arrays.fill(cache, NEBOLO_POCITANE);

                // Trivialny pripad
                cache[0] = 0;

                // Na vyplnenie policka na indexe s spravime presne to, co rekurzivny
                // kod spravi pri volani minVyplatenie(s)
                for (int s = 1; s <= suma; s++) {
                        int minPocet = Integer.MAX_VALUE;
                        for (int i = 0; i < hodnotyCP.length; i++) {
                                if (s - hodnotyCP[i] < 0)
                                        continue;

                                int pom = cache[s - hodnotyCP[i]];
                                if (pom == NEDA_SA)
                                        continue;

                                minPocet = Math.min(minPocet, pom);
                        }

                        int vysledok;
                        if (minPocet == Integer.MAX_VALUE)
                                vysledok = NEDA_SA;
                        else
                                vysledok = minPocet + 1;

                        // Narozdiel od rekurzivneho kodu hodnotu nevratime, ale len ulozime
                        // do cache.
                        cache[s] = vysledok;
                }

                return cache[suma];
        }

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

        public static void main(String[] args) {
                BankaDP statnaPokladnica = new BankaDP(new int[] { 100, 500, 800 });
                System.out.println(statnaPokladnica.minVyplatenieDP(10000000));
        }
}

package prednaska07;

public class BankaBacktrack {
    // 100, 500, 800
    private int[] hodnotyCP;
    // napr. 9x, 2x, 3x
    private int[] poctyCP;

    private int suma;
    private int minimalneVyplatenie = Integer.MAX_VALUE;

    public BankaBacktrack(int[] hodnotyCP) {
        this.hodnotyCP = hodnotyCP.clone();
        this.poctyCP = new int[hodnotyCP.length];
    }

    private void spracuj() {
        int celkovyPocetPapierov = 0;
        int celkovaSuma = 0;
        for (int i = 0; i < poctyCP.length; i++) {
            celkovaSuma += poctyCP[i] * hodnotyCP[i];
            celkovyPocetPapierov += poctyCP[i];
        }


        if (celkovaSuma == suma) {
            if (celkovyPocetPapierov < minimalneVyplatenie) {
                minimalneVyplatenie = celkovyPocetPapierov;
            }
        }
    }

    private void generuj(int odIdx) {
        if (odIdx == poctyCP.length) {
            spracuj();
            return;
        }

        // ake mam moznosti pre konkretny cenny papier hodnotyCP[odIdx]

        for (int pocetKusov = 0; pocetKusov <= suma / hodnotyCP[odIdx]; pocetKusov++) {
            //pocet += pocetKusov;
            poctyCP[odIdx] = pocetKusov;
            generuj(odIdx + 1);
            //pocet -= pocetKusov;
        }

    }

    // vrati celkovy pocet pouzitych cennych papierov
    public int minVyplatenie(int suma) {
        this.suma = suma;
        generuj(0);

        if (minimalneVyplatenie == Integer.MAX_VALUE) {
            return -1;
        } else {
            return minimalneVyplatenie;
        }
    }


    public static void main(String[] args) {
        BankaBacktrack b = new BankaBacktrack(new int[]{100, 500, 800});
        System.out.println(b.minVyplatenie(1100));
    }
}
 

package prednaska07;

import sk.upjs.calltree.CallTree;

import java.util.Arrays;

public class BankaRekurzia {

    private int[] hodnotyCP;

    private int[] cache;

    private static final int NEDA_SA = -1;
    private static final int NEBOLO_POCITANE = -2;

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

    public int minVyplatenie(int suma) {
        if (suma < 0) {
            return NEDA_SA;
        }

        if (cache[suma] != NEBOLO_POCITANE) {
            return cache[suma];
        }

        if (suma == 0) {
            return 0;
        }
        //CallTree.markCall(suma);
        int minimum = Integer.MAX_VALUE;
        for (int i = 0; i < hodnotyCP.length; i++) {
            int res = minVyplatenie(suma - hodnotyCP[i]);
            if (res == NEDA_SA) {
                continue;
            }
            if (res < minimum) {
                minimum = res;
            }
        }

        int vysledok;
        if (minimum == Integer.MAX_VALUE) {
            vysledok = NEDA_SA;
        } else {
            vysledok = minimum + 1;
        }
        cache[suma] = vysledok;
        return vysledok;
    }

    public int minimalneVyplatenieCache(int suma) {
        cache = new int[suma + 1];
        Arrays.fill(cache, NEBOLO_POCITANE);
        return minVyplatenie(suma);
    }

    public static void main(String[] args) {
        BankaRekurzia b = new BankaRekurzia(new int[]{100, 500, 800});
        System.out.println(b.minimalneVyplatenieCache(11000000));
    }
}
 

package prednaska07;

public class BankaDP {

    private int[] hodnotyCP;
    private static final int NEDA_SA = -1;
    private static final int NEBOLO_POCITANE = -2;

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

    public int minVyplatenie(int suma) {
        int[] dp = new int[suma + 1];
        // trivialny pripad
        dp[0] = 0;

        for (int s = 1; s <= suma; s++) {
            int minimum = Integer.MAX_VALUE;
            for (int i = 0; i < hodnotyCP.length; i++) {
                if (s - hodnotyCP[i] < 0) continue;

                int res = dp[s - hodnotyCP[i]];
                if (res == NEDA_SA) {
                    continue;
                }
                if (res < minimum) {
                    minimum = res;
                }
            }

            if (minimum == Integer.MAX_VALUE) {
                dp[s] = NEDA_SA;
            } else {
                dp[s] = minimum + 1;
            }


        }

        return dp[suma];
    }

    // DP[i] - minimalny pocet cennych papierov potrebnych na vyplatenie sumy i

    public static void main(String[] args) {
        BankaDP b = new BankaDP(new int[]{1, 5, 8});
        System.out.println(b.minVyplatenie(5000000));
    }
}