Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: Mkusyn1 05. 03. 2020, 06:44:04

Název: Algoritmus výplně gridu
Přispěvatel: Mkusyn1 05. 03. 2020, 06:44:04

Ahoj všem,

Mám obrázky které jsou násobky jednotky gridu. Typ 1 = čtverec, typ 2 = dva čtverce vedle sebe (obrázek na šířku ), typ3 dva čtverce pod sebou (obrázek na výšku).

Dale mám grid o libovolném počtu sloupců, min 2 a max 8. A počtu řádku, které odpovídají min. požadavků na vyplnění obrázky.

Přiznam se, že ani po dni jsem neprisel na algoritmus, ktery dokáže vyplnit grid obrázky tak, aby byl vždy řádek vyplněn.

Jako příklad : Mám-li 3 obrázky typu 1 a jeden typu 2, tak pro grid o šíři 4, v případě výplně podle pořadí, se obrázek typu 2 dostane až na druhý řádek a poslední sloupec řádku 1 zůstane prázdný.

Název: Re:Algoritmus výplně gridu
Přispěvatel: linuxak 05. 03. 2020, 07:18:23

Nevím, jestli jsem zadání pochopil úplně správně, ale připadá mi to jako Multi-dimensional knapsack problem (https://en.wikipedia.org/wiki/Knapsack_problem#Multi-dimensional_knapsack_problem) a jaké to má důsledky, to už se dočteš na wikipedii.

Název: Re:Algoritmus výplně gridu
Přispěvatel: kvas 05. 03. 2020, 08:17:25

Citace: linuxak  05. 03. 2020, 07:18:23

Nevím, jestli jsem zadání pochopil úplně správně, ale připadá mi to jako Multi-dimensional knapsack problem (https://en.wikipedia.org/wiki/Knapsack_problem#Multi-dimensional_knapsack_problem) a jaké to má důsledky, to už se dočteš na wikipedii.

... a pre upresnenie, jedna sa o klasicky 2D cutting stock problem - vid google. Je to dost komplexna problematika, hoci na prvy pohlad to nevyzera velmi zlozito.

pokial hladas algoritmus, ktory ti najde optimalne riesenie, tak to bude dost problem (google: NP-hard), ak by si stacila heuristika, doporucujem tieto odkazy:

https://codeincomplete.com/posts/bin-packing/
https://blackpawn.com/texts/lightmaps/
https://github.com/juj/RectangleBinPack/blob/master/RectangleBinPack.pdf
https://github.com/juj/RectangleBinPack

Název: Re:Algoritmus výplně gridu
Přispěvatel: xyz 05. 03. 2020, 08:46:39

A jsou jen ty 3 typy obrazku? 1x1, 1x2, 2x1 ? Protoze pak to poskladat urcite lze a neni to ani zadny optimalizacni problem podle me.

Název: Re:Algoritmus výplně gridu
Přispěvatel: xyz 05. 03. 2020, 08:56:59

Citace: ondrama  05. 03. 2020, 08:46:39

A jsou jen ty 3 typy obrazku? 1x1, 1x2, 2x1 ? Protoze pak to poskladat urcite lze a neni to ani zadny optimalizacni problem podle me.

Jo aha, sorry, pises nasobky, tak nic...

Název: Re:Algoritmus výplně gridu
Přispěvatel: alex6bbc 05. 03. 2020, 09:26:48

uplne jsem nepochopil zda mas zadane poradi jak za sebe ty obrazky skladat?
protoze pokud mas zadane poradi, tak nemas moc co resit, vkladas je dokud ti staci sloupce
a postupne vyplujes radky.

pokud nezalezi na poradi obrazku, pak to je ten cutting nebo knapsack problem.