B6

package sk.upjs.paz.cvicenie06;

import java.util.Arrays;

public class Zlodeji {

    // tu budu tie 0 a 1 - 0 znamena ze prvy zlodej berie, 1 druhy zlodej berie
    private int[] pole;

    /// 2 3 5 ..
    private int[] hodnoty;
    private int celkovaSuma;

    private int najmensiRozdiel = Integer.MAX_VALUE;
    private int[] najlepsiaKonfiguracia;

    public Zlodeji(int[] hodnoty) {
        this.hodnoty = hodnoty;
        for (int i = 0; i < hodnoty.length; i++) {
            celkovaSuma += hodnoty[i];
        }
        this.pole = new int[hodnoty.length];
    }

    private void generuj(int odIndex) {
        if (odIndex == pole.length) {
            spracuj();
            return;
        }

        pole[odIndex] = 0;
        generuj(odIndex + 1);
        pole[odIndex] = 1;
        generuj(odIndex + 1);
    }

    private void spracuj() {
        // pole [0, 1, 1, 0, 1]
        // hodnoty [2, 3, 5, 8, 11]
        int sumaPrveho = 0;
        for (int i = 0; i < pole.length; i++) {
            if (pole[i] == 0) {
                sumaPrveho += hodnoty[i];
            }
            //sumaPrveho += hodnoty[i] * pole[i];
        }
        int rozdiel = Math.abs(sumaPrveho - (celkovaSuma - sumaPrveho));
        if (rozdiel < najmensiRozdiel) {
            najmensiRozdiel = rozdiel;
            najlepsiaKonfiguracia = pole.clone();
        }

    }

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

    private void vypisVysledok() {
        System.out.println("Najmensi rozdiel je " + najmensiRozdiel);
        System.out.println(Arrays.toString(najlepsiaKonfiguracia));
        System.out.println("prvy zlodej berie ");
        for (int i = 0; i < najlepsiaKonfiguracia.length; i++) {
            if (najlepsiaKonfiguracia[i] == 0) {
                System.out.println(hodnoty[i]);
            }
        }
    }


    public static void main(String[] args) {
        int[] hodnoty = {2, 3, 5, 8, 11};
        Zlodeji z = new Zlodeji(hodnoty);
        z.generuj();
        z.vypisVysledok();
    }


}

package sk.upjs.paz.cvicenie06;

import java.util.Arrays;

public class NepriatelskeCisla {

    public static void main(String[] args) {
        int[] input = {2, 3, 5, 8, 25};
        boolean chcemVypis = true;
        int pocetRieseni = vyries(input, chcemVypis);
        System.out.println("Pocet rieseni je " + pocetRieseni);
    }

    private static int vyries(int[] input, boolean chcemVypis) {
        int[] output = new int[input.length];
        boolean[] pouzite = new boolean[output.length];
        return generuj(0, input, output, pouzite);

    }

    private static int generuj(int odIdx, int[] input, int[] output, boolean[] pouzite) {
        if (odIdx == output.length) {
            return spracuj(output);
        }
        int pocetRieseni = 0;
        for (int i = 0; i < input.length; i++) {
            if (!pouzite[i]) {
                pouzite[i] = true;
                output[odIdx] = input[i];
                pocetRieseni += generuj(odIdx + 1, input, output, pouzite);
                pouzite[i] = false;
            }
        }
        return pocetRieseni;
    }

    private static int spracuj(int[] output) {
        for (int i = 1; i < output.length; i++) {
            if (suNepriatelske(output[i], output[i - 1])) {
                return 0;
            }
        }
        // je to korektne
        System.out.println(Arrays.toString(output));
        //pocitadlo++;
        return 1;
    }

    private static boolean suNepriatelske(int a, int b) {
        return (a % b == 0) || (b % a == 0);
    }

}
 

package sk.upjs.paz.cvicenie06;

import java.util.Arrays;

public class NepriatelskeCisla2 {

    private int[] input;
    private int[] output;
    private boolean[] pouzite;
    private int pocitadlo = 0;

    public NepriatelskeCisla2(int[] input) {
        this.input = input;
        output = new int[input.length];
        pouzite = new boolean[output.length];
        generuj(0);
        System.out.println(pocitadlo);
    }

    public static void main(String[] args) {
        int[] input = {2, 3, 5, 8, 25};
        new NepriatelskeCisla2(input);
    }

    private void generuj(int odIdx) {
        if (odIdx == output.length) {
            //spracuj(output);
            System.out.println(Arrays.toString(output));
            pocitadlo++;
            return;
        }

        for (int i = 0; i < input.length; i++) {
            // idem dosadit cislo input[i] do pola output[odIdx]

            if (!pouzite[i] && (odIdx == 0 || !suNepriatelske(output[odIdx - 1], input[i]))) {
                pouzite[i] = true;
                output[odIdx] = input[i];
                generuj(odIdx + 1);
                pouzite[i] = false;
            }
        }
    }

    private void spracuj(int[] output) {
        for (int i = 1; i < output.length; i++) {
            if (suNepriatelske(output[i], output[i - 1])) {
                return;
            }
        }
        // je to korektne
        System.out.println(Arrays.toString(output));
        pocitadlo++;

    }

    private static boolean suNepriatelske(int a, int b) {
        return (a % b == 0) || (b % a == 0);
    }

}
 

package sk.upjs.paz.cvicenie06;

public class ZlodejiBinarne {

    public static void main(String[] args) {
        int[] hodnoty = {2, 3, 5, 8, 11};
        int sucet = 0;
        for (int i = 0; i < hodnoty.length; i++) {
            sucet += hodnoty[i];
        }
        int najmensiRozdiel = Integer.MAX_VALUE;
        for (int i = 0; i < 1 << (hodnoty.length); i++) {
            int sucetPrveho = 0;
            for (int j = 0; j < hodnoty.length; j++) {
                if ((i & (1 << j)) == 0) {
                    sucetPrveho += hodnoty[j];
                }
            }
            int rozdiel = Math.abs(sucetPrveho - (sucet - sucetPrveho));
            if (rozdiel < najmensiRozdiel) {
                najmensiRozdiel = rozdiel;
            }

        }
        System.out.println(najmensiRozdiel);
    }
}