Mamy  przedmiotów i plecak o udźwigu  W powyższym drzewie masa przedmiotu oznaczona jest liczbą kwadracików pod numerem przedmiotu, np.  zaś

Przedstawiany jest on m.in. w następującej wersji:

Rozwiązanie tego problemu korzysta z metody programowania dynamicznego. Mamy tablicę  na początku zainicjowaną wartościami  Kolejne przedmioty rozpatrujemy w kolejnych fazach algorytmu. Będziemy utrzymywali niezmiennik, że po -tej fazie algorytmu  jeśli spośród przedmiotów ze zbioru  możemy wybrać podzbiór  o łącznej masie  Ponadto  będzie największym numerem przedmiotu, który można umieścić w pewnym

Odpowiedzią jest, oczywiście, największe  takie że  Nasze rozwiązanie działa w czasie  i pamięci

W praktyce jednak, wybierając się na wycieczkę, pakujemy do plecaka rzeczy, biorąc pod uwagę ich przydatność, a nie tylko to, jak imponująco będzie wyglądał nasz plecak. W szczególności niektóre z przedmiotów są bezużyteczne, jeśli w plecaku nie znajdą się z innymi, np. wzięcie na wakacje statywu nie jest zbyt mądre, jeśli nie weźmiemy aparatu fotograficznego. I właśnie z tą ciut praktyczniejszą wersją problemu plecakowego musieli zmierzyć się uczestnicy finału Potyczek Algorytmicznych 2012. Dla każdego przedmiotu  został określony inny przedmiot  bez którego przedmiot  będzie bezużyteczny (albo  jeśli  jest przedmiotem przydatnym samym w sobie). Pytamy znów, jak ciężki plecak możemy zapakować, nie przekraczając jego udźwigu i nie zabierając żadnego bezużytecznego przedmiotu.

Zależności między przedmiotami możemy przedstawić jako drzewo: dla każdego przedmiotu  tworzymy krawędź skierowaną z węzła  do węzła (patrz rysunek). Dodajemy także sztuczny przedmiot numer  o wadze  Widzimy, że aby można było zapakować do plecaka przedmiot  muszą tam znaleźć się wszystkie przedmioty na ścieżce od węzła  w górę drzewa.

Okazuje się, że problem można rozwiązać całkiem prosto, ale wymaga to pewnej dozy pomysłowości i na zawodach udało się to tylko dwóm z 20 zawodników. Będziemy przeglądać przedmioty w kolejności występowania ich w drzewie w porządku preorder (czyli w kolejności przechodzenia drzewa w głąb – dla ułatwienia przenumerujmy te przedmioty, jeśli ich kolejność jest inna). Rozważamy przedmiot  i pytamy się o warunek istnienia upakowania  o masie  przedmiotami ze zbioru  jeśli bierzemy przedmiot  ale nie bierzemy żadnego bezużytecznego przedmiotu. Załóżmy, że istnieje poprawne upakowanie plecaka przedmiotami  o masie  i że  jest największym możliwym numerem przedmiotu w   Zauważmy, że jeśli  to w oczywisty sposób  jest poprawnym upakowaniem. Podobnie jeśli (czyli węzeł  znajduje się w poddrzewie zaczepionym w lewym bracie węzła ), to ponieważ  zawiera wszystkie przedmioty na ścieżce od  do korzenia, więc zawiera również przedmiot  zatem znowu bierzemy  Jeśli natomiast  to oznacza, że żadne upakowanie o masie  nie może zawierać przedmiotu  czyli upakowanie  nie może istnieć.

Zaimplementowanie nowego rozwiązania wymaga jedynie kosmetycznej zmiany w poprzednim programie: