[C++] Knapsack - pravokotniki

za narest imam algo, ki bo mnozico (VSE) pravokotnikov cim bolj tesno popakiral v cimmanj "velikih" pravokotnikov (holder). vsi pravokotniki (item) imajo velikost stranice 2ⁿ, kar zna poenostaviti vso zadevo. algoritm naj bi imel nastavitev, koliko "truda" (packing VS time) naj vlozi. recimo za nek preview nas ne zanima optimalnost ampak samo hiter rezultat, cez vikend pa nej racuna kolikor hoce. se en stvar, ki bi jo bilo potrebno upostevati je "prijateljstvo" pravokotnikov. namrec, nekateri si zelijo biti cim bolj skupaj (v enem holderju recimo).

greedy algo je recimo hiter (bojda :p), kak genetski algo pa pocasen. rabim pa kompromis.

ideje ter implementacije na plano :p

Iščeš s požrešnim algoritmom, potem pa izvajaš lokalno optimizacijo (nekaj pravokotnikov rukneš iz nahrbtnika in ga ponovno poskušaš zapolniti; če je rešitev boljša staro zavržeš in nadaljuješ).
Seveda rešitev skoraj gotovo ni optimalna.

PS: Algoritmi in podatkovne strukture ?

@cc
aps? ne...

@snow
:p

@hash
optimalnost bi skorajda bila nujna, v mejah neke normale seveda (90% recimo).

prva stvar, ki se mi zdi, da je potrebna, je sestavljanka. namrec, kako vzdrzevat zapolnjenost enega holderja.

struct rect {
   int x1,y1,x2,y2;
};

class holder {
  int sizex,sizey;
  // 
  array<rect>  aUsed;
  array<rect>  aFree;
  //
  holder()
  {
     aFree.add(0,0,sizex,sizey);
  }
};

vsakic, ko dodamo en rect v holder, le ta preparsa seznam prostih pravokotnikov ter ga v enega izmed njih doda. operacija "vrivanja" razreze en pravokotnik (v aFree) na vec manjsih (0..8?).

Hja ... v tem primeru je finta.

Maš 2^n stranice in nek dovolj "praktični" primer. Kar zagotavlja, da premnogo različnih inputov ni. Zato lahko za vse - magari bruta forca - izračunaš optimume vnaprej.

Kaj češ sparat RAM, da prazen gnije?

Če rabiš nastavljat natančnost vs. hitrost in ti je všeč greedy algoritem, potem ga enostavno spremeni v beam search. Ko je širina beama imaš greedy, ko je zadosti velika pa kar iskanje v širino.

Sicer ne vem če sem ti zdej kej novga povedu ... :)