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

• #8969 sztanozs veterán peterszky #8956

  Új Válasz 2015-09-17 16:34:29 #8969

  Ú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

  

  sztanozs

  veterán

  válasz peterszky #8956 üzenetére

  Nekem ez jött ki backtrack-kel:
  119709
  84657
  68233
  50364
  12047
  3650
  2136
  1553
  1470
  891

  A megoldást (excel vba) majd feltolom valahová.

• #8958 axioma veterán peterszky #8956

  Új Válasz 2015-09-16 11:11:44 #8958

  Ú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

  

  axioma

  veterán

  válasz peterszky #8956 üzenetére

  Ismetlesnel arra gondoltam, hogy ugyanaz az index 2x lehet-e (egy szam - ha csak 1x van is - felhasznalhato-e ketszer), de gondolom akkor nem.
  Ja, hogy az 1%-ot ugy erted, hogy akkor nem jon ki, amikor a (melysegi) kereses nem talalja meg az elejen... azaz nem is nem jon ki, hanem nem varjatok ki.
  Ha ezek penzosszegek, akkor gondolom lehet felso korlat a szummara, mondjuk 10M. Teged pedig legfeljebb a 10M alatti osszes szam _egyfele_ osszeallitasa erdekel. DE: az egyes ertekekhez me'g erre sincs szukseged. Eleg az utolso elemet tudni, ami kellett ahhoz, hogy o osszealljon. (Az egyikben.)
  Szoval reszemrol a kovetkezo algot probalnam be:
  map int->int
  indulaskor 0->0
  csokkeno sorrendben a szamok, mindegyiknel a map minden elemehez hozzaadod, es ha kisebb a celszamnal es nincs me'g benne, akkor beteszed az uj szamot rendelve hozza.
  amikor megkapod a celszamot pont, akkor abort, es visszakeresed: a map-ben milyen szamot irtal melle, kivonod a celszamobol azt, es keresed a map-ben a maradekot. Ismetled amig a 0->0-hoz nem jutsz. Voila, megvan a keresett halmaz.
  Ez igy ordo max^2*darabszam ordo max^2*ln(max)*darabszam (a map koltsegigenye miatt) komplexitas idoben, es ordo max tarhelyben. Azt neked kell tudnod, hogy ez belefer-e.
  Ilyesfajta megoldasra gondoltal?

• #8957 sztanozs veterán peterszky #8956

  Új Válasz 2015-09-16 11:08:17 #8957

  Ú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

  

  sztanozs

  veterán

  válasz peterszky #8956 üzenetére

  szvsz ha van megoldás, sima backtack-kel megoldható: a legmagasabbtól indulva, összeadva, amíg nagyobb vagy egyenlő nem lkesz, aztán ha nagyobb, akkor backtack. Ha a backtack után (vagy akár az első lépésben) összes elérhető szám összege kisebb, mint kívánt, akkor nincs megoldás.
  Amúgy csak pontos megoldás jöhet szóba (range nem)?

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