Proc by nebylo ? Ted to je O((n+max(pocet_v_baleni))^2)
Pridavam predelany kod ktery respektuje vyse zminenou diskuzi
<?
// definice baleni dle zadani. Klic je pocet ks, hodnota je cena za ks
$baleni=array(1=>20,5=>18,10=>19,50=>17);
// zadany pocet ks
$ks=78;
// priznak zda muzu vyhodit nejake kusy. Napriklad celkova cena pro 49 je vetsi nez pro 50ks
// vyplati se koupit 50 a 1 vyhodit
$muzuvyhazovat=true;
// nadale budu pouzivat baleni od nejvetsiho poctu kusu v baleni. Na objednavce to bude vypadat lepe.
krsort($baleni);
// kontrola jestli je zadane baleni 1ks. To zaruci moznost poskladat jakykoliv pocet ks
// cena za nejmensi baleni - budu ji potrebovat
end($baleni);
$nejmensibalenicena=current($baleni)*key($baleni);
if (!isset($baleni[1])) {
if ($muzuvyhazovat) {
// naplnim baleni mensi nez nejmensi s tim ze se musi vyhodit nejake kusy
for ($i=key($baleni)-1;$i>=1;$i--) {
$baleni[$i]=$nejmensibalenicena;
}
} else {
// zkontroluju zda to muzu vubec dodat z dannych baleni
$deleno=false;
foreach ($baleni as $pocet=>$tmp)
if (!$deleno and ($ks % $pocet==0)) $deleno=true;
if (!$deleno) die("pocet neni mozno poskladat z moznych baleni");
}
}
// pokud je pocet ks vetsi nez nejmensi spolecny nasobek baleni (nsnb), staci pocitat optimalni ceny pro nsbn a zbytek po deleni
// poctu nsbn. Napr. pokud chci 738 baleni a nsnb je 70, tak vysledek bude 10*cena(nsnb)+cena(38)
// Proc? protoze mnozstvi nsbn lze poskladat z kterehokoliv baleni, lze ho poskladat i z baleni s nejnizi cenou za kus
// nebudu tady psat eukliduv algoritmus at to neni dlouhe, spokojim se s kratkym orientacnim vypoctem. Kdyztak si ho sem dopiste.
$nsnb=1;
foreach ($baleni as $pocet=>$tmp)
if (($nsnb % $pocet) !=0) $nsnb*=$pocet;
// pocet kombinaci ktery musim spocitat. Je to bud ks nebo nsbn - co je mensi
$n=$ks<$nsnb?$ks:$nsnb;
// jestli muzu vyhazovat, pridam jeste nejvetsi baleni k vypoctu
reset($baleni);
if ($muzuvyhazovat) $n+=current($baleni);
/* ceny je pole, kde budu ukladat navrhy kombinaci pro jednotlive pocty.
* klic bude pocet, hodnoty budou mit nasledujici strukturu
* cena .. celkova cena
* index .. prvni index ze ktereho se sklada. Pokud jde o baleni, nebude existovat
* viz nasledny vypocet. Druhy index je pocet-index. Napr. 42 s indexem 15 znamena ze
* se sklada z vypoctenych kombinaci baleni 15 a (42-15) tj. 27
* pokud muzu vyhazovat, a bude index zaporny, znamena to ze mam koupit klic - index a zbytek vyhodit
*/
$ceny=array();
// baleni 1ks je nutno vzit z definice.
if (isset($baleni[1])) {
$ceny[1]["cena"]=$baleni[1];
} else {
$ceny[1]["cena"]=$nejmensibalenicena*2;
}
// vyplnim hodnoty pro vsechny ostatni pocty az po n
for ($i=2;$i<=$n;$i++) {
// kazde baleni lze vyjadrit jako kombinaci dvou jinych baleni o mensich mnozstvich
// je jasne ze kombinaci je mnozstvi/2. A take je jasne ze jedna z techto kombinaci je nejlepsi
// jako vychozi nejlepsi kombinaci ulozim soucet baleni 1 a o 1 mensi nez hledane
$nejindex=1;
$nejcena=$ceny[1]["cena"]+$ceny[$i-1]["cena"];
// staci prohledavat do poloviny hodnoty
for ($j=2;$j<intval($i/2);$j++) {
if ($nejcena>$ceny[$j]["cena"]+$ceny[$i-$j]["cena"]) {
$nejcena=$ceny[$j]["cena"]+$ceny[$i-$j]["cena"];
$nejindex=$j;
}
}
// ted zjistim jestli nahodou neni baleni o hledanem mnozstvi a nema lepsi cenu nez nalezena kombinace
// pozor musim dat na prepocet celkove ceny a ceny za kus
if (isset($baleni[$i]) and ($baleni[$i]*$i<$nejcena)) {
// mam baleni a vychazi lepe
$ceny[$i]["cena"]=$baleni[$i]*$i;
} else {
// ne, je potreba to poskladat
$ceny[$i]["cena"]=$nejcena;
$ceny[$i]["index"]=$nejindex;
}
}
// v pripade ze mam povoleno vyhazovat, zjistim jestli je vyssi cena pro nizsi index. Pokud ano, tak nastavuju zaporny index
if ($muzuvyhazovat) {
for ($i=$n-1;$i>=1;$i--)
if ($ceny[$i+1]["cena"]<=$ceny[$i]["cena"]) {
// vyplati se vyhodit, vyhazuju i v pripade ze je cena stejna
if (!isset($ceny[$i+1]["index"]) or ($ceny[$i+1]["index"]>0)) {
// je to cele baleni, napr. 50ks, nebo kladny index v baleni
$ceny[$i]["index"]=-1;
} else {
// uz o 1 vyssi pocet je lepe vyhodit, takze index dam rovnou na to puvodni
// napr zkoumam 48. 49 melo index -1 a ukazovalo na 50. Spoctena cena je porad vyssi nez pro 50, index dam -2 (=-1-1)
$ceny[$i]["index"]=$ceny[$i+1]["index"]-1;
}
// a dosadim novou cenu
$ceny[$i]["cena"]=$ceny[$i-$ceny[$i]["index"]]["cena"];
}
}
// ted musim udelat vysledky
// do pole objednat naskladam vsechny indexy baleni, hodnota bude pocet baleni
// nastavim na 0
$objednat=array();
foreach ($baleni as $pocet=>$tmp) $objednat[$pocet]=0;
// na naplneni si udelam rekurentni funkci (zabere to mene radku)
// misto global to muze byt predavano odkazem, tohle je hezci
function pridej($mnozstvi) {
global $objednat,$ceny;
if (!isset($ceny[$mnozstvi]["index"])) {
// je to cele baleni
$objednat[$mnozstvi]++;
} else {
pridej($mnozstvi-$ceny[$mnozstvi]["index"]);
if ($ceny[$mnozstvi]["index"]>0) {
// u slozeneho bez vyhazovani i druhou cast
pridej($ceny[$mnozstvi]["index"]);
}
}
}
// pokud je ks>nsnb tak nejprve pridam nsnb nasobene poctem nsnb v ks
$x=$ks;
if ($x>$nsnb) {
pridej($nsnb);
$nasob=intval($ks/$nsnb);
foreach ($objednat as $pocet=>$tmp) $objednat[$pocet]*=$nasob;
$x-=$nasob*$nsnb;
}
pridej($x);
// uz jen ukazat vysledky
$celkem=0;
echo "Objednavka:<hr>\n";
foreach ($objednat as $pocet=>$chceme)
if ($chceme) {
echo "$chceme x baleni $pocet ks<br>\n";
$celkem+=$baleni[$pocet]*$pocet*$chceme;
}
echo "<hr>CELEKEM $celkem penez<br>\n";
?>
159 Odpovědí
54844 Zhlédnutí