Új hozzászólás Aktív témák

• #6436 modder aktív tag peterszky #6435

  Új Válasz 2013-01-04 12:13:36 #6436

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  modder

  aktív tag

  válasz peterszky #6435 üzenetére

  Hasonlít a hátizsák problémára:
  legyenek a számok súlyok. A hátizsákok az 1. listabeli elemek, maximális súly kapacitásuk pedig a szám.
  A téglák a 2. listabeli elemek, súlyuk szintén maga a szám, értékük pedig legyen annál nagyobb, minél nagyobb a szám: tehát lehet maga a szám az érték is. Ez azért jó, mert ha úgy pakolsz egy hátizsákba, hogy nagyobb téglákat használsz, azzal kevesebbet is egyben, így nagyobb lesz a valószínűsége annak, hogy a kisebb értékekből a többi zsákot meg tudod tömni: mert több kisebb értékből több kombinációt tudsz összehozni.

  A probléma az, hogy amíg egy zsákos problémára van optimális algoritmus, addig a több zsák egy NP-teljes probléma, amire nincsen egzakt algoritmus. Elfogadható időben csak egy közelítőleg jó megoldást tudsz találni.
  A probléma inkább erre hasonlít: http://en.wikipedia.org/wiki/Bin_packing_problem

  Ott van is két algoritmus.

  Jó lenne tudni, hogy az 1. listabeli elemeket MINDIG ki lehet-e rakni teljesen a 2. listabeli elemekből, mert ha nem, akkor be kell vezetni egy mércét, ami értékeli a megoldást: Minél több 1. listabeli elemet tettünk ki; Minél több számot használtunk fel teljesen a 2. listából; Az 1. listabeli teljesen kirakott elemek összege maximális;

  Nézd meg a fenti linket.

Új hozzászólás Aktív témák