Dyskretny problem plecakowy - czy to wystarczy?

Witam...

Mam do napisania projekt rozwiązujący dyskretny problem plecakowy.

Projekt napisałem, ale nie jestem pewny czy jest kompletny...

otóż...
Program tam sobie wczytuje przedmioty, sortuje je w sposób nierosnący po zł/kg, potem podaje wagę max plecaka i dodaje elementy (od najcenniejszych) sprawdzając oczywiście czy mieszczą się w plecaku...

Na wikipedii znalazłem zdanie "Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem w którym jest przedmiot o największej wartości[2]."

Czyli nie wystarczy, że powkładam do plecaka od najcenniejszych rzeczy do najmniej cennych?
Coś muszę jeszcze sprawdzać? dzięki za infoo

pozdrawiam

Twój sposób jest całkowicie błędny. Tak nie rozwiązuje się DYSKRETNEGO problemu plecakowego. Żadne "sprawdzenie na koniec" nie pomoże.

Powiedzmy, że masz następujące przedmiotu:
cena waga
3 3
3 3
5 4

i masz plecak 6l.
Po posortowaniu i wybraniu najbardziej wartościowego uzyskasz tylko 5. Natomiast optymalne rozwiązanie to 3+3.

masz rację... 2 opcje:

Brutalnie przeszukiwać bądź zastosował programowanie dynamiczne...

Pozdrawiam