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.
Hladanie minima z moznych suctov
-
audiotrack
VIP
- Príspevky: 25958
- Registrovaný: 09 sep 2005, 18:39
- Kontaktovať používateľa:
Re: Hladanie minima z moznych suctov
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
- Príspevky: 3894
- Registrovaný: 24 feb 2005, 21:26
- Bydlisko: Senec
- Kontaktovať používateľa:
Re: Hladanie minima z moznych suctov
audiotrack to the rescue 
znie to rozumne a pre moj jednoduchy mozog aj zrealizovatelne. Dakujem za tip, vyskusam, pohram sa s tym. Mas u mna holuba
znie to rozumne a pre moj jednoduchy mozog aj zrealizovatelne. Dakujem za tip, vyskusam, pohram sa s tym. Mas u mna holuba
-
audiotrack
VIP
- Príspevky: 25958
- Registrovaný: 09 sep 2005, 18:39
- Kontaktovať používateľa:
Re: Hladanie minima z moznych suctov
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);
?>