Istnieją dwie wersje tego problemu. Możemy założyć, że dysponujemy nieograniczoną ilością każdej z rzeczy, wtedy mówimy o ogólnym problemie plecakowym. Jeżeli każdy przedmiot występuje jeden raz, to mówimy o decyzyjnym problemie plecakowym.

W celu lepszego zrozumienia zadania warto postawić się w miejscu handlarza, który idzie na targ z plecakiem. Sprzedawca wie, że wszystko co zaniesie sprzeda za określoną cenę. Jego celem jest tak zapakować plecak, aby mógł go unieść, a wartość przedmiotów była jak największa.

Ogólny Problem Plecakowy

Ogólny problem plecakowy polega, aby spakować tak przedmioty, aby ich wartość była największa. Przed rozpoczęciem pakowania jest dokładnie wiadomo ile jest różnych przedmiotów, ile każdy waży oraz jaką mają wartość. W ogólnym problemie plecakowym liczba rzeczy jest nieograniczona tj. dany przedmiot możemy brać tyle razy ile chcemy. W przypadku, gdy dany przedmiot możemy wziąć tylko raz to mamy do czynienie z decyzyjnym problem plecakowym.

Przykład

Przypuśćmy teraz, ze mamy dane 4 przedmioty, których waga i wartość są jak w tabelce. Trzeci wiersz zawiera wyliczoną opłacalność, która nie będzie wprowadzona przez użytkownika, a zostanie wyliczona w trakcie wykonywania programu:

Przdmiot	Wartość	Waga	Opłacalność
1	3	1.5	2
2	2.5	5	0.5
3	1	1	1
4	1	5	0.2

Jak widać handlarz powinien zabrać jak najwięcej przedmiotów oznaczonych numerem 1, a najmniej przedmiotów z numerem 4, ponieważ ważą dużo, a są niewiele warte. Przed rozpoczęciem zliczania ile jakich przedmiotów handlarz ma spakować warto posortować listę malejąco względem opłacalności:

Przedmiot	Wartość	Waga	Opłacalność
1	3	1.5	2
3	1	1	1
2	2.5	5	0.5
4	1	5	0.2

Rozpocznijmy teraz pakowanie plecaka. Wiemy, że do plecaka można spakować maksymalnie wagę U. Na potrzeby przykładu załóżmy, że U = 13. Wtedy sprawdzamy dla pierwszego przedmiotu ile sztuk możemy spakować. W tym przypadku można spakować, aż 8 sztuk. Symulując włożenie przedmiotów do plecaka należy pamiętać, aby zmniejszyć U o iloczyn ile sztuk przedmiotu włożono i zwiększając wartość Wspakowanych przedmiotów, tj.: U = 13 – 12 = 1, a W = 8 * 3 = 24.

W plecaku nie zmieści się już żaden przedmiot 1, dlatego ten sam zestaw operacji należy wykonać dla kolejnych przedmiotów. Przedmiot mniej opłacalny ma numer 3 i wejdzie dokładnie jedna sztuka, a do plecaka już nie da rady włożyć więcej przedmiotów, ponieważ U wynosi 0, ponieważ jeden przedmiot waży 1. Wartość całkowita plecaka zwiększa się w ten sposób o 1, czyli W = 25. Podsumowując udało się zapakować plecak w pełni i uzyskać wartość W = 25.

Decyzyjny Problem Plecakowy

Decyzyjny problem plecakowy to przypadek problemu plecakowego, który polega na zmaksymalizowaniu wartości plecaka C bez przekraczania maksymalnej wagi W. W odróżnieniu od ogólnego przypadku każdy wymieniony przedmiot można spakować tylko raz. Jednak jeśli przedmiot występuje na liście n razy to n razy można go spakować. Zadanie to najlepiej odwzorowuje rzeczywistość.

Przykład

Przykładowo załóżmy, że maksymalnie można do plecaka włożyć W = 7kg. do spakowania są przedmioty w tabelce. Dla każdego z wymienionych przedmiotów wyliczmy iloraz C_i do W_i.

Przedmiot	Cena	Waga	Opłacalność (Ci / Wi)
1	10	2	5
2	6	3	2
3	2	4	0.5
4	3	5	0.6
5	3	1	3
6	1	1	1

Kolejny krok polega na posortowaniu listy według opłacalności:

Przedmiot	Cena	Waga	Opłacalność (Ci / Wi)
1	10	2	5
5	3	1	3
2	6	3	2
6	1	1	1
4	3	5	0.6
3	2	4	0.5

W ostatnim etapie należy określić, które przedmioty zostaną zabrane. Przedmioty są wybierane od tych najbardziej opłacalnych. Jeśli przedmiot można spakować to jest on dokładany do plecaka.

Przedmiot	Cena	Waga	Do zabrania?	Pozostały Udźwig W’
1	10	2	Tak	7-2=5
5	3	1	Tak	5-1=4
2	6	3	Tak	4-3=1
6	1	1	Tak	1-1=0
4	3	5	Nie	–
3	2	4	Nie	–

Ostatnie dwa elementy nie muszą być już sprawdzane, ponieważ i tak nie zmieszczą się do plecaka. Ta drobna optymalizacja pozwoli zakończyć działanie algorytmu wcześniej. Wynikiem działania algorytmu jest zwrócenie, że do plecaka należy spakować przedmioty o numerach 1, 3, 5 i 6. Wartość plecaka Cwyniesie 10 + 3 + 6 + 1 = 20.