Problem plecakowy z ujemnymi wartościami

Odpowiedz Nowy wątek
2020-01-14 11:13
0

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.

Pozostało 580 znaków

2020-01-14 11:41
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.


It's easy to hate code you didn't write, without an understanding of the context in which it was written.

Pozostało 580 znaków

2020-01-14 11:55
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

Pozostało 580 znaków

2020-01-14 12:56
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];
            }

        }

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0