Hladanie minima z moznych suctov

Ak neviete kam zaradiť Váš príspevok, použite túto kategóriu...
Holubar
Darca
Darca
Používateľov profilový obrázok
Príspevky: 3894
Registrovaný: 24 feb 2005, 21:26
Bydlisko: Senec
Kontaktovať používateľa:

Hladanie minima z moznych suctov

Príspevok od používateľa Holubar »

Otazka asi idealne pre vysokoskolakov:

Dokopy mam pouzit sucet 11 hodnot z 3 roznych kategorii.

Z kat A mozem pouzit min. 3 a max. 5 hodnot
Z kat. B mozem pouzit min. 2 a max. 6 hodnot
Z kat C mozem pouzit min. 1 a max 3 hodnoty.

Hladam najnizsi mozny sucet 11 hodnot podla vyssie uvedenych kriterii. V skole sme to riesili vyskladanim funkcie a pouzitim niektorej z optimalizacnych metod, ale jednak som v tom bol slaby a zo skoly si aj tak nic nepamatam, tak keby sa tu nasiel nejaky genius, budem mu velmi zaviazany.
audiotrack
VIP
VIP
Používateľov profilový obrázok
Príspevky: 25958
Registrovaný: 09 sep 2005, 18:39
Kontaktovať používateľa:

Re: Hladanie minima z moznych suctov

Príspevok od používateľa audiotrack »

toto by som neriešil optimalizačnými algoritmami, keď sa to dá celkom jednoducho generovať konštruktívne. Výhodou je že robíš súčet (a nie nejaké logaritmy,integrály či zložitejšie operácie ktoré nevieš rozložiť na dve časti) takže vieš, že je optimálne vyberať najnižšie hodnoty z každej skupiny a máš polovicu riešenia. K tomu by si dospel aj optimalizáciou, tak ju rovno môžme preskočiť. Ďalej vieš, že vyberáš minimálne 3+2+1 takže tieto hodnoty z jednotlivých skupín vybereš najnižšie čo tam sú. A ostáva ti doplniť do 11 hodnôt podľa tých kritérii. V každej skupine by som zvyšné hodnoty zoradil a postupne bral a generoval najnižšiu kombináciu. Vôbec nemusíš kontrolovať všetky kombinácie
Holubar
Darca
Darca
Používateľov profilový obrázok
Príspevky: 3894
Registrovaný: 24 feb 2005, 21:26
Bydlisko: Senec
Kontaktovať používateľa:

Re: Hladanie minima z moznych suctov

Príspevok od používateľa Holubar »

audiotrack to the rescue :new05:

znie to rozumne a pre moj jednoduchy mozog aj zrealizovatelne. Dakujem za tip, vyskusam, pohram sa s tym. Mas u mna holuba :smt119
audiotrack
VIP
VIP
Používateľov profilový obrázok
Príspevky: 25958
Registrovaný: 09 sep 2005, 18:39
Kontaktovať používateľa:

Re: Hladanie minima z moznych suctov

Príspevok od používateľa audiotrack »

Kód: Vybrať všetko

<?php

//vygenerujem si náhodné skupiny A-C
$pole = array();
for($i="A"; $i<="C"; $i++){
    for($j=0; $j<=mt_rand(10,30); $j++){
        $pole[$i][] = mt_rand(0,1000);
    }
}



//definujem pocty prvkov spolu a v každej skupine minimum a maximum prvkov
$pocet = array();
$pocet["spolu"] = 11;
$pocet["A"] = array("min"=>3, "max"=>5);
$pocet["B"] = array("min"=>2, "max"=>6);
$pocet["C"] = array("min"=>1, "max"=>3);



$vystup = array();  //sem si budem hádzať výsledok
for($i="A"; $i<="C"; $i++){  //pre každu skupinu hodnôt
    sort($pole[$i]); //zoradím si prvky v skupinach od najnizsieho po najvyssie
    for($j = 1; $j<=$pocet[$i]["min"]; $j++){  //bere minimálny počet prvkov (polia sú zoradené, prvé prvky sú najmenšie)
        $vystup[] = $pole[$i][$j-1];
    }
    //nechám si iba tie prvky čo môžem reálne použiť. Zvyšné ma nezaujímajú. Tzn. použité von, a tie čo sú za "max" tiež von
    $pole[$i] = array_slice($pole[$i], $pocet[$i]["min"], $pocet[$i]["max"]-$pocet[$i]["min"]);
}


//idem dohladať zvyšných (spolu - (sucet min)) prvkov
for($i = 1; $i<=$pocet["spolu"] - count($vystup); $i++){  //pre n hodnôt ktoré mi chýbajú
    //vyberem najmenší prvok /v každom poli mám už len toľko prvkov koľko môžem ešte max použiť/
    $min = PHP_INT_MAX; //hladám minimum, tak si nastavim počiatočnú hodnotu na maximálnu možnú
    $z_pola = "";  //pamätám si z ktorej skupiny beriem
    for($i="A"; $i<="C"; $i++){
       if($pole[$i][0] != NULL && $pole[$i][0] <= $min){  //ak prvok je (nie smo na prázdnej skupine z ktorej som všetko pobral) a je minimálny
           $min = $pole[$i][0];  //tak je to môj kandidát
           $z_pola = $i;
       }
    }   
    $vystup[] = $min; //nasiel som najmenšiu hodnotu, pridám do výstupu   
    $pole[$z_pola] = array_slice($pole[$z_pola], 1); //zmažem hodnotu z možných, aby som ju nepoužil znova
}

echo implode("+",$vystup) . "=" . array_sum($vystup);

?>

kým ty odpíšeš, ja som ti to naprogramoval :) Holuba si poprosím v prezle a americké zemiačky
Napísať odpoveď