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

import java.util.Arrays;

public class Generator {
        /**
         * Pole, v ktorom generujeme postupnost
         */
        private int[] pole;

        /**
         * Spracuje hodnoty v postupnosti - vypise ich
         */
        private void vypis() {
                System.out.println(Arrays.toString(pole));
        }

        /**
         * Generuje variacie s opakovanim v podpoli pocnuc indexom odIndexu
         */
        private void generuj(int odIndexu) {
                if (odIndexu == pole.length) {
                        vypis();
                        return;
                }

                for (int i = 1; i <= 3; i++) {
                        pole[odIndexu] = i;
                        generuj(odIndexu + 1);
                        // Eventualne mozeme vratit obsah pola do povodneho stavu - ale je
                        // to zbytocne...
                        // pole[odIndexu] = 0;
                }
        }

        /**
         * Nastartuje generovanie
         */
        public void generuj() {
                generuj(0);
        }

        public Generator(int k) {
                pole = new int[k];
        }

        public static void main(String[] args) {
                Generator g = new Generator(3);
                g.generuj();
        }
}

import java.io.*;
import java.util.*;

public class Trezor {

        /**
         * Trieda uchovavajuca udaje o jednom predmete
         */
        public static class Predmet {
                int cena;
                int velkost;
        }

        /**
         * Zoznam predmetov v trezore
         */
        List<Predmet> predmety;

        /**
         * Najlepsi najdeny vyber
         */
        private int[] najVyber;
        /**
         * Cena najlepsieho najdeneho vyberu
         */
        private int najCena;

        /**
         * Kapacita batohu
         */
        private int kapacitaBatoha;

        /**
         * Pole, v ktorom generujeme 0 a 1 - vsetky moznosti vyberu
         */
        private int[] vyber;

        /**
         * Spracuje vyber
         */
        private void spracuj() {
                // Pre aktualny vyber spocitame celkovu velkost a celkovu cenu vyberu
                int celkovaVelkost = 0;
                int celkovaCena = 0;
                for (int i = 0; i < vyber.length; i++) {
                        if (vyber[i] == 1) {
                                celkovaVelkost += predmety.get(i).velkost;
                                celkovaCena += predmety.get(i).cena;
                        }
                }

                // Overime, ci sa vyber zmesti do batoha
                if (celkovaVelkost > kapacitaBatoha)
                        return;

                // Ak je aktualny vyber ako najlepsi, co sme doposial mali, tak si ho
                // ulozime
                if (celkovaCena > najCena) {
                        najCena = celkovaCena;
                        najVyber = vyber.clone();
                }

        }

        /**
         * Generuje vsetky mozne vybery pocnuc odIdx-tym predmetom
         */
        private void generuj(int odIdx) {
                if (vyber.length == odIdx) {
                        spracuj();
                        return;
                }

                vyber[odIdx] = 0;
                generuj(odIdx + 1);

                vyber[odIdx] = 1;
                generuj(odIdx + 1);
        }

        public List<Predmet> najlepsiVyber(int kapacita) {
                // Inicializujeme hladanie najlepsieho vyberu
                najCena = 0;
                kapacitaBatoha = kapacita;
                // Vytvorime pole, do ktoreho budeme generovat vysledok
                vyber = new int[predmety.size()];
                // Spustime generovanie
                generuj(0);

                // Vyberieme zoznam predmetov v najlepsom najdenom vybere
                List<Predmet> vysledok = new ArrayList<Predmet>();
                for (int i = 0; i < predmety.size(); i++)
                        if (najVyber[i] == 1)
                                vysledok.add(predmety.get(i));

                return vysledok;
        }

        /**
         * Nacita zoznam predmetov z textoveho suboru
         */
        public void nacitajPredmety(File subor) {
                Scanner citac = null;
                try {
                        citac = new Scanner(subor);
                        predmety = new ArrayList<Predmet>();
                        while (citac.hasNextInt()) {
                                Predmet predmet = new Predmet();
                                predmet.cena = citac.nextInt();
                                predmet.velkost = citac.nextInt();
                                predmety.add(predmet);
                        }
                } catch (Exception e) {
                        System.err.println("Zlyhalo nacitanie suboru " + subor);
                } finally {
                        if (citac != null)
                                citac.close();
                }
        }

        public static void main(String[] args) {
                Trezor trezor = new Trezor();
                trezor.nacitajPredmety(new File("trezor.txt"));
                List<Predmet> vyber = trezor.najlepsiVyber(4);

                // Vypiseme vybrane predmety
                for (Predmet predmet : vyber)
                        System.out.println(predmet.cena + "[" + predmet.velkost + "]");
        }
}

import java.util.Arrays;

public class GeneratorBezOpakovania {
        /**
         * Pole v ktorom generujeme variacie
         */
        private int[] pole;

        /**
         * Pole, v ktorom uchovavame, ci sa hodnota i (i=1..n) nachadza v poli pole.
         */
        private boolean[] uzBolo;

        /**
         * Urcuje velkost mnoziny, z ktorej vytvarame variacie bez opakovania ({1,
         * ..., n})
         */
        private int n;

        private void vypis() {
                System.out.println(Arrays.toString(pole));
        }

        private void generuj(int odIndexu) {
                // Ak sme vygenerovali vsetky hodnoty v poli, tak pole vypiseme
                if (odIndexu == pole.length) {
                        vypis();
                        return;
                }

                for (int i = 1; i <= n; i++) {
                        // Cislo i ulozime do pola, iba ak sa este nenachadza na indexoch
                        // 0..(odIndexu-1)
                        if (!uzBolo[i]) {
                                // Poznacime si pridanie hodnoty i do pola
                                uzBolo[i] = true;
                                pole[odIndexu] = i;
                                // Generujeme variacie bez opakovania od indexu odIndexu+1
                                generuj(odIndexu + 1);
                                // pole[odIndexu] = 0;
                                // Poznacime si odobratie hodnoty i z pola
                                uzBolo[i] = false;
                        }
                }
        }

        public void generuj() {
                generuj(0);
        }

        public GeneratorBezOpakovania(int n, int k) {
                // Ulozime si parameter n
                this.n = n;
                // Vytvorime pole, do ktoreho budeme generovat variacie
                pole = new int[k];
                // Vytvorime pole s indexami 0..n, v ktorom si pre cisla v rozsahu 1..n
                // budeme pamatat, ci sme ich pouzili
                uzBolo = new boolean[n + 1];
        }

        public static void main(String[] args) {
                GeneratorBezOpakovania g = new GeneratorBezOpakovania(4, 3);
                g.generuj();
        }
}