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.
0
1
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.
0
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
0
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];
}
}