Riešenia (skupina D, 6. týždeň)

import java.util.Arrays;

public class Generator {
    /**
     * Pole, v ktorom generujeme postupnost
     */
    private int[] pole;
    private int[] mnozinaCisel = new int[] { 1, 3, 5 };

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

        for (int i = 0; i < pole.length; i++) {
            riadok += mnozinaCisel[pole[i] - 1];
        }
        System.out.println(riadok);
    }

    /**
     * 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;

        /**
         * Rozdelenie predmetov 2 zlodejom
         */
        private List<Predmet> zlodej1 = new ArrayList<Predmet>();
        private List<Predmet> zlodej2 = new ArrayList<Predmet>();

        /**
         * 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();
                }

        }

        int minRozdiel = Integer.MAX_VALUE;

        public void najdiMinimalnyRozdiel() {
                int cenaZlodej1 = 0;
                int cenaZlodej2 = 0;

                for (int i = 0; i < vyber.length; i++) {
                        if (vyber[i] == 1) {
                                cenaZlodej1 += predmety.get(i).cena;
                        } else {
                                cenaZlodej2 += predmety.get(i).cena;
                        }
                }

                int rozdiel = Math.abs(cenaZlodej1 - cenaZlodej2);

                if (rozdiel < minRozdiel) {
                        minRozdiel = rozdiel;
                        najVyber = vyber.clone();
                }
        }

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

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

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

        public void rozdelPredmety() {
                vyber = new int[predmety.size()];
                generuj(0);

                for (int i = 0; i < predmety.size(); i++)
                        if (najVyber[i] == 1)
                                zlodej1.add(predmety.get(i));
                        else
                                zlodej2.add(predmety.get(i));
        }

        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);

                trezor.rozdelPredmety();

                // Vypiseme vybrane predmety pre obidvoch zlodejov
                System.out.print("Ceny predmetov zlodeja1: ");
                for (Predmet predmet : trezor.zlodej1)
                        System.out.print(predmet.cena + " ");
                System.out.print("\nCeny predmetov zlodeja2: ");
                for (Predmet predmet : trezor.zlodej2)
                        System.out.print(predmet.cena + " ");
        }
}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Telesna {

    int[] poleZiakov;
    int[] cislaZiakov;

    public Telesna(int n, Set<Integer> m) {

        this.poleZiakov = new int[n];

        this.cislaZiakov = new int[n];

        int idx = 0;
        for (int cislo : m) {
            this.cislaZiakov[idx] = cislo;
            idx++;
        }

    }

    public void vypisPole() {
        System.out.println(Arrays.toString(poleZiakov));

    }

    public boolean milujuSa (){

        if(poleZiakov[0] % poleZiakov[1]==0) {
            return false;
        }
        for (int i=1; i<poleZiakov.length -1;i++){


            if((poleZiakov[i] % poleZiakov[i-1]==0) || (poleZiakov[i] % poleZiakov[i+1]==0) ){
                return false;
            }

        }
        if(poleZiakov[poleZiakov.length-1] % poleZiakov[poleZiakov.length-2]==0) {
            return false;}

        return true;
    }

    public void generator(int odIdx) {
        if (odIdx == poleZiakov.length) {
            if (milujuSa())
            vypisPole();
            return;
        }
        for (int i = 1; i <= poleZiakov.length; i++) {
            if (moze(odIdx, cislaZiakov[i-1])) {
                poleZiakov[odIdx] = cislaZiakov[i-1];
                generator(odIdx + 1);
            }
        }
    }

    private boolean moze(int poIdx, int hodnota) {
        for (int i = 0; i < poIdx; i++) {
            if (poleZiakov[i] == hodnota) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Set<Integer> m = new HashSet<Integer>();
        m.add(2);
        m.add(4);
        m.add(6);
        m.add(7);
        m.add(9);
        m.add(3);
        m.add(5);
        m.add(8);

        Telesna t = new Telesna(8, m);
        t.generator(0);

    }

}

public class Damy {

        //je dama na policku?
        boolean[][] sachovnica;
        //je ohrozeny riadok?
        boolean[] riadky;
        boolean[] diagH;
        boolean[] diagV;
        int pocet=0;
        int rozmer;
        Damy(int rozmer){
                this.rozmer=rozmer;
                sachovnica=new boolean[rozmer][rozmer];
                riadky=new boolean[rozmer];
                diagH=new boolean[2*rozmer];
                diagV=new boolean[2*rozmer];

        }
        public String toString(){
                String res="";
                for(int i=0;i<rozmer;i++){
                        for(int j=0;j<rozmer;j++){
                                res+=(sachovnica[i][j]?"I":"_");
                        }       
                        res+="\n";
                }
                res+="--------------------------------------\n";
                return res;

        }
        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                Damy d=new Damy(16);
                d.umiestni(0);
                System.out.println(d.pocet);

        }
        private void umiestni(int i) {
                if (i==rozmer){
                        //System.out.println(this);
                        pocet++;
                        return;
                }
                for(int j=0;j<rozmer;j++){
                        if (!riadky[j] && !diagH[j-i+rozmer] && !diagV[j+i]){
                                sachovnica[j][i]=true;
                                riadky[j]=true;
                                diagH[j-i+rozmer]=true;
                                diagV[j+i]=true;
                                umiestni(i+1);
                                sachovnica[j][i]=false;
                                riadky[j]=false;
                                diagH[j-i+rozmer]=false;
                                diagV[j+i]=false;
                        }

                }

        }

}