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

• bambano titán

  #8948

  #8947 peterszky

  2015-09-15 12:55:15

  Új Válasz

  Ú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

  

  bambano

  titán

  #8947 peterszky

  #8947 peterszky

  Van egy valós életbeli problémám, a lényeg, hogy vannak értékek, emellett egy darabszám és egy összeg. A bruteforce megoldás 99%-ban jól működik, de ott az az 1%, ami bármikor bejöhet és mint tudjuk, ez be is jön.

  A lényeg, hogy az alábbi listában a végén látható darabszámban vegyünk ki értékeket úgy, hogy a végén látható összeg kijöjjön.

  Knapsack vagy ennek egy változata volt talán az, amit nézegettem, de egyelőre nem tudom eldönteni, hogy melyik megoldásnak kellene nekiállni, a dinamikus programozás változata ilyen értékeknél, ha jól értelmeztem, akkor elég halál memória szempontból.

  Esetleg valakinek van javaslata, merre lenne érdemes nézelődni még?

  NDX: 0 OSSZEG: 119709
  NDX: 1 OSSZEG: 84657
  NDX: 2 OSSZEG: 68233
  NDX: 3 OSSZEG: 50364
  NDX: 4 OSSZEG: 40664
  NDX: 5 OSSZEG: 37626
  NDX: 6 OSSZEG: 32079
  NDX: 7 OSSZEG: 31902
  NDX: 8 OSSZEG: 28440
  NDX: 9 OSSZEG: 26180
  NDX: 10 OSSZEG: 20632
  NDX: 11 OSSZEG: 20535
  NDX: 12 OSSZEG: 18548
  NDX: 13 OSSZEG: 17824
  NDX: 14 OSSZEG: 16424
  NDX: 15 OSSZEG: 16406
  NDX: 16 OSSZEG: 15864
  NDX: 17 OSSZEG: 14909
  NDX: 18 OSSZEG: 14907
  NDX: 19 OSSZEG: 14131
  NDX: 20 OSSZEG: 13956
  NDX: 21 OSSZEG: 12374
  NDX: 22 OSSZEG: 12047
  NDX: 23 OSSZEG: 11621
  NDX: 24 OSSZEG: 11269
  NDX: 25 OSSZEG: 11230
  NDX: 26 OSSZEG: 10917
  NDX: 27 OSSZEG: 10316
  NDX: 28 OSSZEG: 9826
  NDX: 29 OSSZEG: 9690
  NDX: 30 OSSZEG: 9594
  NDX: 31 OSSZEG: 9367
  NDX: 32 OSSZEG: 8231
  NDX: 33 OSSZEG: 8056
  NDX: 34 OSSZEG: 7779
  NDX: 35 OSSZEG: 7454
  NDX: 36 OSSZEG: 6947
  NDX: 37 OSSZEG: 6877
  NDX: 38 OSSZEG: 6501
  NDX: 39 OSSZEG: 6325
  NDX: 40 OSSZEG: 6147
  NDX: 41 OSSZEG: 6147
  NDX: 42 OSSZEG: 6074
  NDX: 43 OSSZEG: 5791
  NDX: 44 OSSZEG: 4039
  NDX: 45 OSSZEG: 3682
  NDX: 46 OSSZEG: 3650
  NDX: 47 OSSZEG: 3639
  NDX: 48 OSSZEG: 3159
  NDX: 49 OSSZEG: 2610
  NDX: 50 OSSZEG: 2331
  NDX: 51 OSSZEG: 2256
  NDX: 52 OSSZEG: 2136
  NDX: 53 OSSZEG: 1553
  NDX: 54 OSSZEG: 1470
  NDX: 55 OSSZEG: 891
  NDX: 56 OSSZEG: 235

  DB: 27 OSSZEG: 344710

  nem tudom, hogy mit értesz brute force megoldás alatt, de a brute force azt jelenti, hogy agyatlanul végigpróbálgatod az összes lehetséges verziót és kiválasztod a végeredményt. tehát az mindig megtalálja a megoldást, ha van.

  a mai világban egy 56 elemű listának én brute force módszerrel állnék neki, backtrack egy intelligensebb változatával próbálkoznék. memória nem kell neki sok, a processzorodat agyonüti, de ez engem nem izgatna

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