Problem plecakowy z ujemnymi wartościami

Mam problem z zadaniem. Mam podaną tablice dwu wymiarową z wartościami i wagą przedmiotów. Mam znaleźć największą możliwą wartość mojego plecaka, z tym tylko, że wartości przedmiotów mogą być ujemne, a ja nie mogę nie zapakować przedmiotu jeżeli się on zmieści. Próbowałem podejść do tego normalną dynamiczną metodą ale ona po prostu pomija wartości ujemne. Przykład: Mam cztery elementy (waga/wartość) 1/2 1/5 3/5 1/-5 i plecak mieści 3 wagi. Muszę wziąć przedmiot 3/5 bo gdy wezmę 1/2 i 1/5 muszę też zapakować przedmiot 1/-5 i wartość plecaka wynosi 2.

Intuicja mi mówi że standardowe dynamiczne podejście powinno sobie poradzi z ujemnymi wartościami, jak i zapakowaniem do pełna.
Gdybyś wstawił kod to można by było się pobawić, a tak pozostaje się zdać na intuicje.

O ile się orientuję to dynamiczne podejście nigdy nie zapakuje ujemnej wartości. A kod będę mógł wysłać później :P

int tab[8000][2]={0};
        for(int i=1;i<=n;i++)
        {
            el_w =dane[i-1][0];
            el_v =dane[i-1][1];
            for(int j=1;j<=m;j++)
            {
                tab[j][1]=max(tab[j][0],tab[j-1][1]);
                if(j-el_w>=0)
                {
                    if(tab[j][1]<tab[j-el_w][1]+el_v)
                    {
                        tab[j][1]=tab[j-el_w][0]+el_v;
                        
                    }
                }


            }
            
            for(int j=1;j<=m;j++)
            {
                tab[j][0]=tab[j][1];
            }


        }