Autor Zpráva
Dlahacz
Profil *
Dobrý den,
potřeboval bych poradit, nepotřebuju přímo kód, ale stačí mi pouze metodika toho jak vyřešit následující problém

příklad:

potřebuju zaplnit 120litrů tak, aby byla cena co nejnižší, mám k dispozici

80l balení za 80$
25l balení za 40$
10l balení za 25$

(velikosti i ceny tahám z DB a jsou pokaždé jiné)

optimální řešení by tedy bylo

1x80l 2x25l za 160$

teď mám řešení které vyplivne

1x80l 1x25l 2x10l za 170$

Díky moc za rady, věřím že je někde i hotové řešení, ale vubec netuším jak to hledat.
nightfish
Profil
Vypadá to na obdobu Problému batohu.

Jako první mě napadlo seřadit si balení sestupně podle jednotkové ceny a postupně přidávat balení s nejnižší jednotkovou cenou, než vyrovnám nebo přelezu objemový limit. V případě, že jej vyrovnám, jedná se o nejlepší možné řešení. V případě, že limit přelezu, musím ještě vykoušet varianty s vyšší jednotkovou cenou, jestli to náhodou nevyjde lépe...
Keeehi
Profil
Neexistuje (zatím) algoritmus, který to zvládne v polynomiálním čase. Takže nic moc efektivního není. Můžeš vyzkoušet všechny kombinace. Pak to jde taky řešit dynamickým programováním. Žádný zázrak to však taky není.
tiso
Profil
Dlahacz: a tých 120 si získal odkiaľ? Môžeš tam mať hodnotu, ktorá sa nedá vyskladať z dostupných balení? Musíš vyskladať presný objem, alebo ho môžeš prekročiť (2 x 80l je tiež za 160$)?
Dlahacz
Profil *
120 je z uživatelského vstupu, muze se tam zadat jakakoliv hodnota, objem se muze klidne prekrocit.

jdu to zkusit postupem od uzivatele Node na webtrhu

"1. vypocitas si najlepsi pomer cena/objem a usporiadas od najlepsieho po najhorsi
2. vezmes ten najlepsi a nim videlis pozadovany objem na cele cislo.
3. ak to neostal zvysok, parada, koniec.
4. ak ti ostal zvysok, vezmes druhy variant v poradi z bodu 1 a zopakujes bod 2 na tom zvysku.
5. ak je dany variant z bodu 1 privleky na zvysok, prejdi na dalsi variant z bodu 1 a zopakuj az kym ti neostane 0 alebo zvysok.
6. opakuj 2 az 5 na zvysku kym nedojdes k nule"
tiso
Profil
Dlahacz: aha, vlastne som si neuvedomil že už v tých svojich riešeniach ten objem prekračuješ.
Ten algoritmus má pár zlých bodov.
Dlahacz
Profil *
tiso:
mužes to prosím trošku rozepsat? díky moc


Dlahacz:
jo teď koukám, že je to uplně to samé co mám teď vlasně a neřeší to můj problém
tiso
Profil
Dlahacz: jediná možnosť ako zistiť najnižšiu cenu je prejsť si všetky kombinácie balení, ktorými splníš objednávku:
1. vytvoríš kombinácie
2. spočítaš ceny
3. vyberieš kombináciu s najnižšou cenou
Keeehi
Profil
Ten algoritmus z 5 bude dávat celkem dobré výsledky, ale nezaručuje, že to bude nejlepší možné řešení.
Dlahacz
Profil *
Tak jsem na to asi přišel

1. sežadím podel poměru cena/vel. baleni
2. vemu první: požadovaný objem vydělím velikostí balení rozdělím na celé číslo a zbytek
3. (teď ta finta) pokud je zbytek roven nebo větší než zaokrouhleno dolů{cena balení / cena následujícího balení} * velikost následujícího balení / cena balení přičtu k celému číslu +1 a mám hotovo, pokud na krok 4.
4. opakuju to samé pro další velikost balení s tím že místo požadovaného objemu použiju zbytek požadovaného objemu (požadovaný objem nebo zbytek požadovaného objemu z předchozího kroku - celé číslo z předchozího kroku * vel balení z předchozího kroku) , krom posledního v posledním balení krok 5.
5. zbytek požadovaného objemu vydělím vel. balení a zaokrouhlím nahoru

dofám že jsem se do toho nezamodal, díky tomu to postupu jsem dokonce zjistil, že jsem přehlídl v příkladu, že by za těch 160$ šlo koupit i 2x80l :D

díky za rady

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: