A7

import java.util.ArrayList;
import java.util.List;

public class Vyplatenie {

        public static void vypisStlpec(boolean[][] p, int stlpecIdx) {
                for (int i = 0; i < p.length; i++) {
                        if (p[i][stlpecIdx])
                                System.out.print(i + ": T ");
                        else
                                System.out.print(i + ": F ");
                }

                System.out.println();
        }

        public static List<Integer> najdiVyplatenie(int[] hodnotaPlatidla, int suma) {
                boolean[][] d = new boolean[suma + 1][hodnotaPlatidla.length + 1];
                d[0][0] = true;

                vypisStlpec(d, 0);
                // pp = pocet platidiel
                for (int pp = 1; pp <= hodnotaPlatidla.length; pp++) {
                        for (int s = 0; s <= suma; s++) {
                                /*
                                 * d[s][pp] = d[s][pp - 1] || ((s >= hodnotaPlatidla[pp - 1]) &&
                                 * d[s - hodnotaPlatidla[pp - 1]][pp - 1]);
                                 */

                                d[s][pp] = d[s][pp - 1];
                                if ((s - hodnotaPlatidla[pp - 1] >= 0)
                                                && (d[s - hodnotaPlatidla[pp - 1]][pp - 1])) {
                                        d[s][pp] = true;
                                }
                        }

                        vypisStlpec(d, pp);
                }

                if (!d[suma][hodnotaPlatidla.length]) {
                        return null;
                }

                List<Integer> vysledok = new ArrayList<Integer>();
                for (int pp = hodnotaPlatidla.length; pp > 0; pp--) {
                        // viem, ze na d[suma][i] je true
                        if (d[suma][pp - 1] == false) {
                                // musel som pouzit platidlo na indexe pp-1
                                vysledok.add(hodnotaPlatidla[pp - 1]);
                                suma = suma - hodnotaPlatidla[pp - 1];
                        }
                }

                return vysledok;
        }

        public static boolean najdiVyplatenie2(int[] hodnotaPlatidla, int suma) {
                boolean[] d = new boolean[suma+1];
                d[0] = true;
                for (int i=0; i<hodnotaPlatidla.length; i++) {
                        // pribudlo mi hodnotaPlatidla[i]
                        for (int s=d.length-1-hodnotaPlatidla[i]; s>=0; s--) {
                                if (d[s] == true) {
                                        d[s + hodnotaPlatidla[i]] = true;
                                }
                        }
                }

                return d[suma];
        }

        public static void main(String[] args) {
                int[] p = { 2, 5, 2, 10, 3 };
                int suma = 6;
                System.out.println(najdiVyplatenie(p, suma));
        }

}

import java.util.ArrayList;
import java.util.List;

public class Vyplatenie {

        public static void vypisStlpec(boolean[][] d, int stlpec) {
                for (int r = 0; r < d.length; r++) {
                        if (d[r][stlpec]) {
                                System.out.print(r + ": T ");
                        } else {
                                System.out.print(r + ": F ");
                        }
                }
                System.out.println();
        }

        public static List<Integer> daSaZaplatit(int suma, int[] platidla) {
                boolean[][] d = new boolean[suma + 1][platidla.length + 1];
                d[0][0] = true;
                // pp = pocet prvych pouzitych platidiel
                vypisStlpec(d, 0);
                for (int pp = 1; pp <= platidla.length; pp++) {
                        int poslednePlatidlo = platidla[pp - 1];
                        for (int s = 0; s <= suma; s++) {
                                d[s][pp] = d[s][pp - 1]
                                                || ((s >= poslednePlatidlo) && d[s - poslednePlatidlo][pp - 1]);
                        }

                        vypisStlpec(d, pp);
                }

                if (!d[suma][platidla.length]) {
                        return null;
                }

                List<Integer> voVyplateni = new ArrayList<Integer>();
                for (int pp = platidla.length; pp > 0; pp--) {
                        // vieme vyplatit sumu suma ...
                        // vieme, ze d[suma][pp] je true
                        if (d[suma][pp - 1] == false) {
                                // musime pouzit platidlo platidla[pp-1]
                                voVyplateni.add(platidla[pp - 1]);
                                suma = suma - platidla[pp - 1];
                        }
                }

                return voVyplateni;
        }

        public static boolean daSaZaplatit2(int suma, int[] platidla) {
                boolean[] d = new boolean[suma + 1];
                d[0] = true;
                for (int i = 0; i < platidla.length; i++) {
                        for (int s = suma - platidla[i]; s >= 0; s--) {
                                if (d[s] == true)
                                        d[s + platidla[i]] = true;
                        }
                }

                return d[suma];
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                int[] platidla = { 3, 5, 2, 3, 2 };
                int suma = 10;

                System.out.println(daSaZaplatit(9, platidla));
        }

}