Optimální algoritmus výpočtu

Optimální algoritmus výpočtu
« kdy: 16. 08. 2010, 11:30:04 »
Zdravím, potřeboval bych pomoci z vytvořením optimálního algoritmu.

Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:

bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.
Takže v tomto případě 1*bal4, 5*bal2, 3*bal1.
Napadá vás jiné řešení než zkoušet všechny možné kombinace a poté vyhodnotit která je nejvýhodnější. Je to časově celkem náročné.
Díky.
« Poslední změna: 27. 09. 2010, 12:18:12 od Petr Krčmář »


eDISCO

Re: Optimální algoritmus výpočtu.
« Odpověď #1 kdy: 16. 08. 2010, 11:39:45 »
Ahoj,

chcelo by to specifikaciu nejakeho prostredia/jazyku v ktorom to ma byt vytvorene, no kazdopadne skus prevod z arabskych cislic do rimskych.
google: decimal to roman algorithm

JaPe

Re: Optimální algoritmus výpočtu.
« Odpověď #2 kdy: 16. 08. 2010, 11:55:35 »
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0


Re: Optimální algoritmus výpočtu.
« Odpověď #3 kdy: 16. 08. 2010, 11:57:46 »
Ahoj,

chcelo by to specifikaciu nejakeho prostredia/jazyku v ktorom to ma byt vytvorene, no kazdopadne skus prevod z arabskych cislic do rimskych.
google: decimal to roman algorithm
Melo by to byt pro PHP.
A převod z arabskych cislic do rimskych neni stejna uloha ktera je popsana.

Re: Optimální algoritmus výpočtu.
« Odpověď #4 kdy: 16. 08. 2010, 12:05:12 »
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0
Takto to mám uděláno teď ale ve specifických případech to nefunguje.
např.
bal1 (1ks, 100kč/ks)
bal2 (7ks, 10kč/ks)
bal3 (20ks 9kč/ks)
a zákazník požaduje 21ks

dle tohoto by vyšlo 1*bal3 + 1*bal1 výsledná cena 280kč
správně by mělo být 3*bal2 výsledná cena 210kč


Adam

Re: Optimální algoritmus výpočtu.
« Odpověď #5 kdy: 16. 08. 2010, 12:09:30 »
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0

To nebude vzdy fungovat, napriklad pokud by byly ceny nasledujici:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

A zakaznik si bude chtit koupit 6ks, tak pri koupi bal2 a bal1 zaplati 52kc a pri koupi 3x bal3 51kc...

JaPe

Re: Optimální algoritmus výpočtu.
« Odpověď #6 kdy: 16. 08. 2010, 12:26:21 »
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0
Takto to mám uděláno teď ale ve specifických případech to nefunguje.
např.
bal1 (1ks, 100kč/ks)
bal2 (7ks, 10kč/ks)
bal3 (20ks 9kč/ks)
a zákazník požaduje 21ks

dle tohoto by vyšlo 1*bal3 + 1*bal1 výsledná cena 280kč
správně by mělo být 3*bal2 výsledná cena 210kč

Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.

Re: Optimální algoritmus výpočtu.
« Odpověď #7 kdy: 16. 08. 2010, 12:34:31 »
Citace
Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.
Takové balení samozřejmě nalézt jde ale co s ním pak. Jaké balení vyhodit z předchozího výpočtu a nahradit novým, výhodnějším??

JaPe

Re: Optimální algoritmus výpočtu.
« Odpověď #8 kdy: 16. 08. 2010, 12:42:40 »
Citace
Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.
Takové balení samozřejmě nalézt jde ale co s ním pak. Jaké balení vyhodit z předchozího výpočtu a nahradit novým, výhodnějším??
Grr - já to nedopsal:
1) Najít balení s co nejmenším počtem kusů, jehož cena za kus je menší, než průměrná  dle prvního kroku a zopakovat celý algoritmus s tím, že začneš od tohoto balení.
2) To celé dokola, dokud existuje balení s cenou za kus menší než průměr z předchozího kroku a zároveň s počtem kusů menším, než požadovaný.

Re: Optimální algoritmus výpočtu.
« Odpověď #9 kdy: 16. 08. 2010, 12:51:11 »
Tak to vypadá že je to podobná úloha této.
http://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu

takže žádné triviální řešení asi nebude  :-\

Re: Optimální algoritmus výpočtu.
« Odpověď #10 kdy: 16. 08. 2010, 12:53:33 »
Citace
Grr - já to nedopsal:
1) Najít balení s co nejmenším počtem kusů, jehož cena za kus je menší, než průměrná  dle prvního kroku a zopakovat celý algoritmus s tím, že začneš od tohoto balení.
2) To celé dokola, dokud existuje balení s cenou za kus menší než průměr z předchozího kroku a zároveň s počtem kusů menším, než požadovaný.
Zkusím o tom ještě zauvažovat. Možná to nebude úplně 100%ní ale lepší než metoda celočíselného dělení a rychlejší než rekurzivní zkoušení kombinací.

j.

Re: Optimální algoritmus výpočtu.
« Odpověď #11 kdy: 16. 08. 2010, 14:29:22 »
Toto je typycky NP-uplny problem, zadne reseni s polynomialni slozitosti zname neni. Kdyz ale pohledas na google, mozna najdes nejake velice tricky subexponencialni reseni, vzhledem k pozadavkum (internetovy obchod, pocty radove v desitkach az stovkach kusu) je asi exponencialni reseni porad nejjednodussi. Proste fakt zkousej vsechno se vsim.

Re: Optimální algoritmus výpočtu.
« Odpověď #12 kdy: 16. 08. 2010, 15:29:24 »
Pro zajímavost zde je kód který používám
Kód: [Vybrat]
class Variation {
var $pieces_arr=array();
var $prices_arr=array();
var $sum_count=0;
var $sum_price=0;

function Variation() {

}

function setPieces($type, $count, $price){
$this->pieces_arr[$type] = $count;
$this->prices_arr[$type] = $count*$price;
$this->sum_count = array_sum($this->pieces_arr);
$this->sum_price = array_sum($this->prices_arr);
}
}

class VariationSolver {
var $itemsArr = array();
var $reqCount = 0;
var $BestVar;

function VariationSolver() {
$this->BestVar = null;
}

function setRequestedCount($count){
$this->reqCount = $count;
}

function addVariationItem($type, $piece, $price){
$this->itemsArr[] = array($type, $piece, $price);
}

function compute($level, $VarObj){
$max_level = sizeof($this->itemsArr)-1;
$increment = $this->itemsArr[$level][1];
for ($i = 0; $i==0 || ($i <= $this->reqCount && ($VarObj->sum_count+$increment)<=$this->reqCount) ; $i=$i+$increment) {
$VarObj->setPieces($this->itemsArr[$level][0], $i, $this->itemsArr[$level][2]);

if ($max_level>$level){
$this->compute($level+1, $VarObj);
}
else {
if ($VarObj->sum_count==$this->reqCount){
if ($this->BestVar == null || $VarObj->sum_price < $this->BestVar->sum_price){
$this->BestVar = $VarObj;
}
}
}
}
}

function getBestVar(){ //slow
$this->BestVar = null;
if (sizeof($this->itemsArr)>0){
$this->compute(0, new Variation());
}
return $this->BestVar;
}
}

//==== Vypocet ====
$VS = new VariationSolver();
$VS->setRequestedCount(100);
$VS->addVariationItem("N",1,100);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("B",2,95);     // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("A1",5,90);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("D",10,98);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC1",20,81);  // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC2",50,80);  // typ baleni, pocet kusu v baleni, cena za kus

print "<pre>";
print_r( $VS->getBestVar() );
print "</pre>";

pedro

Re: Optimální algoritmus výpočtu.
« Odpověď #13 kdy: 17. 08. 2010, 19:04:55 »
Typicky laboratorni syndrom :-D Vazne veris, ze muze v realnem svete existovat/prodavat se baleni 1 ks za 100 Kc, kdyz baleni 7 ks stoji 70 Kc?
Jinak problem muze nastat i v realu v mnohem mensich radech, ale jenom tehdy, kdyz uspora dosazena koupi nejvyhodnejsiho baleni je nizsi, nez rozdil ceny baleni potrebneho pro dosazeni pozadovaneho poctu a dalsich vyhodnych baleni, ktere jsme nevzali.

Výše uvedený příklad od Adama:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

Pri koupi bal2 je uspora proti bal3 5 * 0,50 = 2,50 a 2,50 je mensi, nez 12 - 8,50 = 3,50. V 99% procentech pripadu vyjde, ze uspora je vyssi a nebudes muset resit dalsi moznosti, takze takovy pristup by mel byt vypocetne mene narocny, nez zkouset vsechno se vsim, tedy za predpokladu, ze pocet moznych baleni je vyssi, nez 3 v nasem pripade ;-)

Re: Optimální algoritmus výpočtu.
« Odpověď #14 kdy: 17. 08. 2010, 21:36:33 »
Typicky laboratorni syndrom :-D Vazne veris, ze muze v realnem svete existovat/prodavat se baleni 1 ks za 100 Kc, kdyz baleni 7 ks stoji 70 Kc?
Jinak problem muze nastat i v realu v mnohem mensich radech, ale jenom tehdy, kdyz uspora dosazena koupi nejvyhodnejsiho baleni je nizsi, nez rozdil ceny baleni potrebneho pro dosazeni pozadovaneho poctu a dalsich vyhodnych baleni, ktere jsme nevzali.

Výše uvedený příklad od Adama:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

Pri koupi bal2 je uspora proti bal3 5 * 0,50 = 2,50 a 2,50 je mensi, nez 12 - 8,50 = 3,50. V 99% procentech pripadu vyjde, ze uspora je vyssi a nebudes muset resit dalsi moznosti, takze takovy pristup by mel byt vypocetne mene narocny, nez zkouset vsechno se vsim, tedy za predpokladu, ze pocet moznych baleni je vyssi, nez 3 v nasem pripade ;-)
Samozrejme vim ze tato situace v realu by nastat nemela. jen jsem zvolil takto vysoke cislo kvuli nazornosti.
Stale nechavam puvodni jednodussi algorytmus zalozeny na celociselnem deleni ktery pro 99% situaci bude optimalni. jen jsem zde chtel zjistit zda neexistuje 100% metoda ktera neni vypocetne narocna, coz asi neni.