| Autor | Zpráva | ||
|---|---|---|---|
| anonym_ Profil * |
Ahoj,
potřeboval bych nakopnout ohledně algoritmu na výpočet ideální (nejnižší) ceny na základě zadaných parametrů. Příklad, poměrně reálný, který potřebuji řešit je následující: - máme 3 délkové varianty produktu - každá varianta produktu má jinou cenu za metr (navíc u různých produktů může být rozdíl větší/menší, není striktně daný) - máme celkovou délku, kterou potřebujeme pokrýt Příklad produktu 1m - 45 Kč 3m - 119 Kč 5m - 179 Kč Zákazník potřebuje koupit 8,1m délky. Varianty, které se letmo nabízí 5+3+1m v ceně 343 Kč. 2x5m v ceně 358 Kč 3x3m v ceně 357 Kč atd. Jak lze strojově najít všechny možné varianty, aby se dala udělat kalkulace, které variatny koupit? U tohohle příkladu těch kombinací nebude mnoho, ale pokud zákazní bude chtít 150m produktu, počet možných kombinací roste. Jak se tento typ úloh řeší, odkud mám začít? Díky. Doplním, že varianty budou nejvýše 3 (abychom se nedostali v této rovině do extrému, že bude 100 variant). |
||
| Firibix Profil |
Reakce na anonyma:
To je klasická úloha na dynamické programování, já bych na ní použil memoizaci: class Calculator {
protected $types = [];
/**
* Memoizacni tabulka
*/
protected $memo = [];
public function __construct(array $types) {
$this->types = $types;
}
public function calculate(int $length) : array {
if ($length <= 0) {
return [0, []];
}
if (isset($this->memo[$length])) {
return $this->memo[$length];
}
$price = null;
$typesToUse = null;
foreach ($this->types as $type => $typePrice) {
$instance = $this->calculate($length - $type);
$instancePrice = $typePrice + $instance[0];
if ($price === null or $instancePrice < $price) {
$price = $instancePrice;
$typesToUse = array_merge($instance[1], [$type]);
}
}
$result = [$price, $typesToUse];
$this->memo[$length] = $result;
return $result;
}
}
// definice variant a jejich cen
$types = [1 => 45, 3 => 119, 5 => 179];
$calculator = new Calculator($types);
$length = 9;
$result = $calculator->calculate($length);
echo 'Pozadovana delka: '.$length.'<br>';
echo 'Nakupte varianty: '.join(', ', $result[1]).'<br>';
echo 'Cena: '.$result[0];Úplně nejefektivnější by samozřejmě bylo použít bottom-up vyplňování tabulky. Ale s ohledem na to, že tvůj problém připouští situace, kdy je levnější koupit v součtu větší délku, než je potřeba, tak by to asi nebylo úplně triviální (v překladu: nechtělo se mi nad tím přemýšlet). Sice bys tím ušetřil overhead rekurze, ale časová složitost by měla být řádově stejná. |
||
| anonym_ Profil * |
Firibix:
Super, vypadá to, že to funguje. Jen na 12. řádku používám `float` místo `int`, jak definované, tak požadované délky, mohou být s desetinnou čárkou. Sice tu funkci po prvním čtení moc nechápu, ale když hýbu s parametry (např. dám 5m jako nejlevnější, což se v akci může klidně stát), tak to i požadované délky 1-4m vrací 1x5m balení. Budu to pak muset otestovat ještě na dalších příkladech, ale zdá se, že to funguje. Než jsem tuhle děkovnou reakci odeslal, napadlo mě ještě jedna varianta, na které ten systém "selže". Tedy, neselže, najde nejmenší cenu, ale v neoptimálním složení. Konkrétně $types = [1 => 10, 3 => 30, 5 => 50]; $length = 11; Za ideální považuji v tomto případě 2x5 + 1x1, nikoliv 11x1. Tenhle příklad, kdy bude stejná cena za m nemusí být úplně běžný, ale nastat může. Tím, že jsem se do té funkce zatím nedokázal vnořit, moc nevidím, kde to upravit. Pomůžeš prosím?Tak asi vyřešeno, výsledek tak, jak potřebuju, vznikne srovnáním pole podle ceny za metr, v tomto případě tedy $types = [5 => 50, 3 => 30, 1 => 10]; Pro můj účel jde o snadnou úpravu a bez nutnosti zasahovat do celého algoritmu. Díky i za klíčové termín "memoizace", případně i ta "bottom-up tabulka". To je to, co jsem hledal. Díky moc! |
||
| Firibix Profil |
#4 · Zasláno: 7. 2. 2021, 11:30:08
Reakce na anonyma:
Metoda calculate se snaží co nejoptimálněji poskládat z dostupných délek tu požadovanou. Dělá to tak, že koupí první variantu, a rekurzivně zavolá sama sebe (řádek 24), aby zjistila, jak co nejlépe poskládat ten zbytek. V tom okamžiku se celý proces opakuje – koupí se první varianta a zjišťuje se, jak co nejlépe poskládat zbytek (tedy požadovaná délka minus koupená varianta). Rekurze končí v okamžiku, kdy je nakoupena požadovaná délka nebo více (řádek 13). Teď se algoritmus vrátí o jeden krok zpět (do okamžiku, kdy kupoval ten poslední kousek, který byl třeba) a zkusí koupit druhou variantu, … Pak je mezi sebou porovná a vybere tu nejlevnější. Následně se rekurze opět vrátí o jeden krok zpět (tedy zbývaly koupit dva kousky) a zjišťuje, jak by to vypadalo, kdyby v tomto okamžiku koupila druhou variantu. Až to zjistí, zase vybere tu nejlevnější a tak se postupně vrací zpět, zkouší všechny možné kombinace, až se dostane k řešení problému s původně zadanou délkou.
„najde nejmenší cenu, ale v neoptimálním složení“ To je pravda, na to jsem nepomyslel. Podmínka na řádku 26 říká, že řešení při koupi jiné varianty, než kterou jsme zkoušeli dříve, je lepší, právě když je levnější. Pokud je cena stejná, necháváme původní. „výsledek tak, jak potřebuju, vznikne srovnáním pole podle ceny za metr“ Tohle pomůže, protože varianty se zkouší v cyklu na řádku 23 v pořadí, v jakém jsou v poli uložené. Tím pádem se jako první najde kombinace 2×5 + 1×1 a až potom kombinace 11×1, která se z důvodů výše nepoužije. Aby se pole nemuselo řadit, šlo by podmínku přepsat tak, že v případě, že jsou ceny stejné, se vezme varianta, která vyžaduje méně kusů: foreach ($this->types as $type => $typePrice) {
$instance = $this->calculate($length - $type);
$instancePrice = $typePrice + $instance[0];
$instanceTypes = array_merge($instance[1], [$type]);
if ($price === null or $instancePrice < $price or ($instancePrice === $price and count($instanceTypes) < count($typesToUse))) {
$price = $instancePrice;
$typesToUse = $instanceTypes;
}
} |
||
| anonym_ Profil * |
#5 · Zasláno: 7. 2. 2021, 12:01:17
Firibix:
Ufff, to vysvětlení je parádní (ani jsi ho nemusel psát tak podrobne, jen bych se musel poradně zadávat do toho kódu, možná i vícekrát). Moc dekuju. Mrknu pak i na ten upraveny kód, byl by obecnější bez nutnosti radit to pole. Ale data, včetně jednotkové ceny mám k dispozici, tak to pro tento konkrétní případ prodeje bude stačit. Ještě jednou moc díky! |
||
|
Časová prodleva: 3 roky
|
|||
0