B7

package sk.upjs.paz.cvicenie07;

import java.util.Arrays;
import java.util.Stack;

public class NVRP {

    public static void main(String[] args) {
        int[] postupnost = {4, 7, 11, 3, 59, 28};
        // d[i] - maximalna dlzka podpostupnosti konciaca na i-tom indexe
        int[] d = new int[postupnost.length];

        // VYPLNENIE POLA D
        for (int i = 0; i < d.length; i++) {
            d[i] = 1;
            for (int j = 0; j < i; j++) {
                // rastuca postupnost, hodnota na i vacsia ako na j
                if (postupnost[i] > postupnost[j]) {
                    d[i] = Math.max(d[i], 1 + d[j]);
                }
            }
        }
        System.out.println(Arrays.toString(d));

        // NAJDENIE VYSLEDKU
        int najdlhsiaPodpostupnost = 0;
        //int indexNajdlhsejPo=0;
        for (int i = 0; i < d.length; i++) {
            if (d[i] > najdlhsiaPodpostupnost) {
                najdlhsiaPodpostupnost = d[i];
                //indexNajdlhsejPo=i;
            }
        }
        System.out.println("najdlhsia vybrana rastuca podpostupnost ma dlzku " + najdlhsiaPodpostupnost);

        // VYPIS RIESENIA
        /*int[] vypis= new int[najdlhsiaPodpostupnost];
        int index=indexNajdlhsejPo;
        int indexVypis= najdlhsiaPodpostupnost-1;
        vypis[indexVypis]=postupnost[index];

        for(int i=index;i>-1;i--){
            if(d[i]==d[index]-1){
                if(postupnost[i]<postupnost[index]){
                    vypis[indexVypis-1]=postupnost[i];
                    indexVypis--;
                    index=i;
                }
            }
        }
        System.out.println(Arrays.toString(vypis));*/
        Stack<Integer> riesenie = new Stack<>();
        int dlzka = najdlhsiaPodpostupnost;
        int aktualnyIdx = postupnost.length - 1;
        while (dlzka > 0) {
            if (d[aktualnyIdx] == dlzka) {
                if (riesenie.isEmpty() || postupnost[aktualnyIdx] < riesenie.peek()) {
                    riesenie.push(postupnost[aktualnyIdx]);
                    dlzka--;
                }
            }
            aktualnyIdx--;
        }
        while (!riesenie.isEmpty()) {
            System.out.println(riesenie.pop());
        }


    }

}
 

package sk.upjs.paz.cvicenie07;

public class Nakup {

    public static void main(String[] args) {

        int c = 28;
        int[] p = {5, 20, 15, 5, 15, 3};
        //int[] p = {2, 1, 3};
        int n = p.length;

        boolean[][] d = new boolean[n + 1][c + 1];
        d[0][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= c; j++) {
                // ak nepouzijem i-te platidlo
                d[i][j] = d[i - 1][j];

                // ak pouzijem i-te platidlo
                if (p[i - 1] <= j) {
                    d[i][j] = d[i][j] || d[i - 1][j - p[i - 1]];
                }
            }
        }
        System.out.println(d[n][c]);

        if (!d[n][c]) {
            System.out.println("Neda sa");
            return;
        }

        System.out.println("viem to vyplatit");
        int zostavajucaSuma = c;
        for (int i = n; i > 0; i--) {
            if (!d[i - 1][zostavajucaSuma]) {
                // neviem vyplatit bez i-teho platidla, takze ho musim pouzit
                System.out.println(p[i - 1]);
                zostavajucaSuma -= p[i - 1];
            }
        }
    }
}
 

package sk.upjs.paz.cvicenie08;

public class Zahradka {

    public static void main(String[] args) {
        // int[riadok][stlpec], i..riadok, j..stlpec, 3riadky*5stlpcov
        int[][] u = {{5, 8, 14, 0, 48}, {1, 150, 7, 2, 1}, {150, 6, 23, 14, 53}};
        int[][] d = new int[u.length + 1][u[0].length + 1];
        for (int i = 1; i <= u.length; i++) {
            for (int j = 1; j <= u[0].length; j++) {
                d[i][j] = u[i - 1][j - 1] + Math.max(d[i - 1][j], d[i][j - 1]);
            }
        }
        System.out.println(d[u.length][u[0].length]);

        StringBuilder vysledok = new StringBuilder();
        int i = u.length;
        int j = u[0].length;
        while (i > 1 || j > 1) {
            if (d[i - 1][j] > d[i][j - 1]) {
                i--;
                vysledok.insert(0, "Dole");
            } else {
                j--;
                vysledok.insert(0, "Vpravo");
            }
        }
        //vysledok.reverse()
        System.out.println(vysledok);
    }
}
 

package sk.upjs.paz.cvicenie07;

import java.util.Arrays;

public class LCS {
    public static void main(String[] args) {
        String s1 = "jevd";
        String s2 = "dva";
        int[][] lcs = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i < s1.length() + 1; i++)
            for (int j = 1; j < s2.length() + 1; j++)
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    lcs[i][j] = 1 + lcs[i - 1][j - 1];
                else
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
        System.out.println(lcs[s1.length()][s2.length()]);
        s1 = "-" + s1;
        System.out.println("   -, d, v, a");
        for (int i = 0; i < lcs.length; i++) {
            System.out.println(s1.charAt(i) + " " + Arrays.toString(lcs[i]));
        }
    }
}