| Autor | Zpráva | ||
|---|---|---|---|
| Dlahacz Profil * |
#1 · Zasláno: 26. 11. 2015, 17:41:49
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 |
#2 · Zasláno: 26. 11. 2015, 18:28:18
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 |
#3 · Zasláno: 26. 11. 2015, 19:04:12
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 |
#4 · Zasláno: 26. 11. 2015, 19:29:49
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 * |
#5 · Zasláno: 27. 11. 2015, 00:16:57
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 |
#6 · Zasláno: 27. 11. 2015, 00:59:47
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 |
#8 · Zasláno: 27. 11. 2015, 02:37:53
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 |
#9 · Zasláno: 27. 11. 2015, 10:40:02
Ten algoritmus z 5 bude dávat celkem dobré výsledky, ale nezaručuje, že to bude nejlepší možné řešení.
|
||
| Dlahacz Profil * |
#10 · Zasláno: 27. 11. 2015, 12:06:54
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 |
||
|
Časová prodleva: 9 let
|
|||
0