Výťah - dynamické programovanie – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Gesler0
Duch
3. 2. 2013   #1
-
0
-

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");
        }
         
    }
}
Nahlásit jako SPAM
IP: 46.29.3.–
Reklama
Reklama
liborb
~ Redaktor
+18
Guru
12. 2. 2013   #2
-
0
-

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í.

Nahlásit jako SPAM
IP: 188.75.135.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 37 hostů

Podobná vlákna

Vytah dat z databaze — založil Petr

Logo soft - výtah — založil Flurry

Programovanie — založil MiReC

Programovanie v c++ — založil kromap426

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý