Rozmístění obrazců v C++ – C / C++ – Fórum – Programujte.com

Zdravím, potřeboval bych poradit s algoritmem (nebo i celým programem klidně). Do programu si naimportuju rozměry obrazců (čtverce a obdélníky) a tyto obrazce bych potřeboval nějakým algoritmem poskládat (rozmístit) a otáčet, aby se mně vešli co nejlépe a nejvíce na určitou velkou zadanou plochu. A na výstup aby mně program napsal počet kolikrát se daný obrazec na plochu vejde. Grafický obrázek by nebyl špatnej, aby daný obrazce zobrazil jak budou rozmístěny na ploše. Na internetu je spousta takových programů, jako je cutting pro, MaxCut V2 atd... Ale žádný tento program neumí z texťáku naiportovat rozměry obrazců a udělat jednoduchý výpis kolikrát se tam daný obrazec vejde.
Můžete mi prosím pomoci s algoritmem a nebo navést na nějaký program který by se dal popřípadě upravit?

No tak nasnadě je hned řešení že načteš všechny obrázky a začneš dělat všechny kombinace nad touhle množinou .. s tím že musíš počítat se složitostí N^N (N je počet obrazců .. a možná ještě horší, když se budou otáčet obrazce) -> jedná se NP uplný problém, který souvisí s optimalizací

Potom bych se podíval po googlu, jestli nejsou nějaký akcelerační algoritmy.

Další věc je taky ta, jestli chceš zkoumat pouze existenci tohoto jevu:

=> ??Existuje taková kombinace krabic, aby se vešla do danné oblasti??

nebo:

=> ??Jaká kombinace je nejlepší a ušetří nejvíce prostoru?? .. průšvih (bude to trvat strašně dlouho, protože musíš prohledat celý stavový prostor)

google: board optimization algorithm

http://stackoverflow.com/…mizing-waste

Třeba tady píšou, že umí import/export CSV. Podle mě by si měl ještě klidně pár dní strávit hledáním než se pouštět do tvorby vlastního.