Knapsack (?) probléma megoldása

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