Aplikace pro farmu rubrika: Programování: Jiné
1
telek
Ahoj všem.
Pro jednu farmu dělám menší aplikaci, kde vstupem je cca 200 balíčků, každý má danou váhu (cca 0,5-2 kg) a druh (žebra, přední-krk, přední-kližka, zadní-kýta, zadní-plec, atd. - jedná se o druhy masa z porážky).
Výstupem jsou krabičky, přičemž každá krabička má obsahovat 4 až 7 balíčků dle několika pravidel. Například celková váha krabičky 5-6 kg, každý druh je v krabičce maximálně jednou, celková váha druhů přední je 1-2 kg, celková váha druhů zadní je 1,5-2,5 kg a další.
Jaký by mohl být algoritmus, který by roztřídil balíčky do krabiček dle uvedených pravidel?
Ideální by bylo projít všechny možné kombinace 4, 5-ti, 6-ti a 7-mi balíčků a vybrat ty kombinace, které odpovídají pravidlům krabičky. Z nalezených krabiček pak najít tolik, aby byly zahrnuty všechny balíčky právě jednou. Ale toto by počítači trvalo spoustu hodin.
Aktuálně to mám tak, že procházím všechny možné kombinace balíčků, ale po nalezení první možné krabičky se další hledá pouze ze zbývajících balíčků. Takto ale zbude asi 25 balíčků, ze kterých už žádná krabička vytvořit nejde. Toto je pro farmu dostačující řešení, ale zajímá mě, jestli by to nešlo ještě lépe, aby byly roztříděny všechny balíčky.
Aplikaci dělám v C#, ale technologie asi není v tomto případě důležitá.
Děkuji
8
rmaslo
Udělal bych ten první nástřel stejně jako to děláš teď.
Pak bych (v cyklu) vybral náhodný volný balíček a náhodnou krabičku a v ní náhodný balíček a zkoumal jestli ty dva balíčky lze vyměnit (aby to neporušilo pravidla té krabičky). Pokud ne, tak nic (continue) a jedu cyklus znovu. Pokud ano, tak vyměnit a prozkoumat jestli z těch volných balíčků lze udělat krabičku. Pokud ne tak nic, pokud ano tak jí udělat. A jedu cyklus znovu.
V cyklu bych počítal průběhy a při vytvoření nové krabičky čítač resetoval. Pokud by čítač byl větší než nějaká hodnota tak bych ten cyklus chcípnul (break) a řeknu, že líp to už nejde.
Tohle je podle mne velmi dobrý algoritmus, když je v každém balíčku stejně krabiček. Což tady ovšem není. Takže by se to ještě mělo vylepšit o to, že se občas na tu výměnu vyberou buď dva balíčky z těch volných nebo naopak dva z té krabičky.
Komentáře
-
telek
:
Díky za tip, zkoušel jsem. Bohužel nejspíš vzhledem k tomu, že balíčky jsou si hodně podobné, tak se sice občas podaří nějaké prohodit, ale další krabičku během rozumné doby už ne.
—
3.8.2020
Pro zobrazení všech 5 odpovědí se prosím přihlaste:
Nebo se přihlaste jménem a heslem:
Komentáře