Algoritmus výplně gridu

Algoritmus výplně gridu
« kdy: 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ý.


Re:Algoritmus výplně gridu
« Odpověď #1 kdy: 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 a jaké to má důsledky, to už se dočteš na wikipedii.

kvas

  • ***
  • 119
    • Zobrazit profil
    • E-mail
Re:Algoritmus výplně gridu
« Odpověď #2 kdy: 05. 03. 2020, 08:17:25 »
Nevím, jestli jsem zadání pochopil úplně správně, ale připadá mi to jako 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

xyz

  • ***
  • 200
    • Zobrazit profil
Re:Algoritmus výplně gridu
« Odpověď #3 kdy: 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.

xyz

  • ***
  • 200
    • Zobrazit profil
Re:Algoritmus výplně gridu
« Odpověď #4 kdy: 05. 03. 2020, 08:56:59 »
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...


alex6bbc

  • *****
  • 1 431
    • Zobrazit profil
    • E-mail
Re:Algoritmus výplně gridu
« Odpověď #5 kdy: 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.