Výťah - dynamické programovanie – Java – Fórum – Programujte.com

Dobrý deň. Riešim úlohu ktorá je veľmi podobná známemu problému batoha. 
Mám danú množinu "hmotnosti", kde sú zadané všetky hmotnosti pasažierov vo výťahu, a nosnosť výťahu. Mám zistiť či je možné všetkých pasažierov dostať na strechu budovy na dva krát. Nechápem moc ale metóde dynamického programovania, pomocou nejakých materiálov z internetu som nakódoval program len neviem, či je daná metóda použitá správne. Moje riešenie by malo obsahovať generovanie všetkých podmnožín ľudí ( s tým mám tiež problém). Mohli by ste mi prosím vás niekto objasniť ako tá metóda dynamického programovania funguje a pozrieť sa na môj zdrojový kód či som ju aplikoval správne? To generovanie všetkých podmnožín ľudí tam ešte nieje a vlastne ani nechápem čo je odomňa žiadané.

public class Vytah {
    //množina hmotnosti cestujucich 
    static int[] hmotnosti = {4, 4, 6, 6, 6, 10};
    //nosnost vytahu
    static int nosnost = 18;
    //inicializacia dvojrozmerneho pola na zapisovanie pomocnych vypoctov
    static int[][] vytah;
    
    public static void main(String[] args) {
        vypocet(hmotnosti, hmotnosti, nosnost);
    }


// a hmotnosti ludi
// b nosnost lodky
// c hodnoty ludi
    static void vypocet(int[] a, int[] c, int b) {
        // premenna vytah je tabulka kde su ulozene vypocty
        vytah = new int[a.length + 1][b];
        
        
        for (int i = 0; i < b; i++) {
            vytah[0][i] = 0;
        }
        int sucet = 0;
        for (int i = 0; i < a.length; i++) {
            sucet += a[i];
        }

        if (sucet > (b * 2)) {
            System.out.println("Vytah neodnesie ludi na strechu");
        } else {
            
            for (int clovek = 1; clovek <= a.length; clovek++) {
                for (int vaha = 1; vaha <= b; vaha++) {

                    if (vaha < a[clovek - 1]) {

                        vytah[clovek][vaha - 1] = vytah[clovek - 1][vaha - 1];

                    } else if (vaha > a[clovek - 1]) {

                        vytah[clovek][vaha - 1] = Math.max(vytah[clovek - 1][vaha - 1], vytah[clovek - 1][vaha - 1 - a[clovek - 1]] + c[clovek - 1]);

                    } else {

                        vytah[clovek][vaha - 1] = Math.max(vytah[clovek - 1][vaha - 1], c[clovek - 1]);

                    }
                }
            }
        }
        int maximum =vytah[a.length][b-1];
        if(maximum == nosnost){
            System.out.println("Vytah odvezie ludi na strechu");
        }
         
    }
}

Dynamické programování je zjednodušeně řečeno vyřešení rekurzivního problému bez rekurze. V tvém případě potřebuješ generovat množiny lidí, které se pokusíš najednou nacpat do výtahu. Generování by mohlo vypadat třeba takto (NE znamená, že v této dílčí úloze daný člověk nepojede a ANO, že pojede):

 NE  NE  NE  NE  NE ANO
 NE  NE  NE  NE ANO  NE
 NE  NE  NE  NE ANO ANO
...
ANO ANO ANO ANO  NE ANO
ANO ANO ANO ANO ANO  NE
ANO ANO ANO ANO ANO ANO

to se dá lehce přepsat na (kde NE=0 a ANO=1):

0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 0 1 1
...
1 1 1 1 0 1
1 1 1 1 1 0
1 1 1 1 1 1

takže testování proběhne od čísla 000001b do čísla 111111b což je od čísla 1 do čísla 63, což bude hlavní cyklus od 1 do 63 včetně.

Následně budeš provádět testy. Když bude nahozený daný bit, tak toho člověka se pokusíš nacpat do výtahu (přičteš jeho váhu do nějaké testovací proměnné, kterou před každým novým počítáním vynuluješ), když tam bude 0, tak nic. Následně zkontroluješ jestli se ta sečtená váha do výtahu vejde a když ano, tak ještě zjistíš, jestli se do druhé svezení vejde váha zbylých lidí (prostým odečtením od celkové váhy všech lidí). A když obě podmínky vyhoví, tak si našel řešení.