[ vedric @ 24.12.2002. 17:09 ] @
Zanima me kako bi se riješio ovaj problemčić..
Imam jednu površinu npr 100 cm x 100 cm i sad bih ja u tu površinu želio upisat kvadrate i pravokutnike različitih dimenzija,od 3 objekta na više,do nekih n objekata.
Algoritam bi trebao biti takav da on te sve kvadrate i pravokutnike tj objekte različitih dimenzija poslaže u tu površinu 100 cm x 100 cm tako da na toj glavnoj površini ostane što manje neiskorištenog prostora.
Treba naći kombinaciju kako bih rekao tog mozaika s najmanje neiskorištenog prostora...

[ drbogi @ 24.12.2002. 20:31 ] @
Jel' bi ti da seces ivericu, ili si se bacio u razmisljanje?

[ Puzo @ 24.12.2002. 20:40 ] @
Postoji jedan veoma slican problem tvom u matematici koji se zove tiling problem. U problemu postoji kvadrat odredjenih dimenzije koji treba poplocati sa fixed tile (tj. poplocati sa samo jednim objektom koji je fiksnih dimenzija). Ukoliko u poslednjih godinu dana nije doslo do nekog novog otkrica, ovaj problem je i dalje neresiv, a resavali su ga mnogi poznati matematicari (npr. Erdos :)))

Nisam siguran (ako gresim, neka me neko ispravi :)), ali mislim da je problem koji si ti naveo je NP-complete problem (tj. trenutno se ne zna da li postoji algoritam u polinomijalnom vremenu koji bi resio navedeni problem). Najbolje resenje ces dobiti samo u slucaju da proveris sve mogucnosti (kojih ima puuuuuuno :))

Trenutno najefikasniji algoritam koji se koristi kako bi resio probleme slicne tiling problemu je first-fit algorithm. Na internetu postoje neke reference oko algoritma.