Opowiada ono o dziwnej wadze Bajtazara, która wyświetla rezultat ważenia zaokrąglony do najbliższej wielokrotności gramów, lub błąd, gdy masa ważonych przedmiotów wynosi co najmniej gramów. Oprócz wagi Bajtazar posiada jeszcze innych przedmiotów. Nie zna ich mas, więc chce je ważyć, używając swojej wagi. Nie określi on oczywiście dokładnych mas swoich przedmiotów. Jednak - być może - ważąc ich podzbiory, dla niektórych par przedmiotów będzie mógł stwierdzić, który z nich jest cięższy. I właśnie o to jesteśmy proszeni: mamy wyznaczyć liczbę takich par, mając dane dokładne masy przedmiotów.

Przeanalizujmy, w jaki sposób Bajtazar może porównywać wagi dwóch przedmiotów. Oznaczmy ich masy przez oraz Weźmy pewien podzbiór pozostałych przedmiotów o masie Jeśli wskazanie wagi będzie inne w przypadku ładunku o masie niż dla ładunku o masie to z całą pewnością można odróżnić wybrane przedmioty.

Załóżmy teraz, że naszych dwóch przedmiotów nie da się porównać w powyższy sposób. Czyli że dla każdego podzbioru pozostałych przedmiotów o masie wskazania wagi dla mas oraz będą takie same. Zauważmy ponadto, że takie samo wskazanie wagi otrzymamy dla ładunku o masie Jeśli zmienimy masy obu rozpatrywanych przedmiotów na to z punktu widzenia Bajtazara nic się nie zmieni! Dla każdego podzbioru przedmiotów Bajtazar otrzyma przecież dokładnie to samo wskazanie wagi zarówno przed i po takiej zmianie. Dowodzi to, że nie może on w żaden sposób rozróżnić mas tych dwóch przedmiotów, gdyż - z jego punktu widzenia - istnieje możliwość, w której ważą one dokładnie tyle samo, czyli

Wiemy już, w jaki sposób Bajtazar może porównywać masy przedmiotów. Do skonstruowania naszego pierwszego algorytmu rozwiązującego zadanie brakuje nam już tylko jednego prostego spostrzeżenia: jeśli wskazania wagi są różne dla ładunków o masach i to będą różne również dla ładunków oraz

Aby sprawdzić, czy Bajtazar może porównać konkretne dwa przedmioty, wystarczy teraz wyznaczyć dla każdego z przedziału najmniejszą masę podzbioru pozostałych przedmiotów postaci a potem sprawdzić, czy któraś z nich jest szukanym rozróżniającym masy i Można zrobić to za pomocą programowania dynamicznego. Przy jego obliczaniu zaktualizowanie informacji o nowy przedmiot zajmuje czas Sprawdzenie jednej pary przedmiotów zadziała w czasie a całe zadanie potrafimy rozwiązać w czasie Złożoność ta nie jest jednak satysfakcjonująca.

Toteż musimy analizować nasz problem dalej. Ustalmy trzy takie przedmioty, że pierwszy jest nieporównywalny zarówno z drugim, jak i z trzecim. Oznaczmy ich masy odpowiednio oraz Możemy teraz zmienić masy pierwszych dwóch przedmiotów na ponieważ są one nieporównywalne i z punktu widzenia Bajtazara nic to nie zmienia. Pierwszy i trzeci przedmiot nadal są nieporównywalne i oczywiście każda inna para przedmiotów o masach oraz również. Ostatecznie Bajtazar nie może rozróżnić masy drugiego i trzeciego przedmiotu. Taka własność relacji bycia nieporównywalnym jest nazywana w matematyce przechodniością. Wraz z innymi w naszym przypadku oczywistymi własnościami zwrotności i symetryczności oznacza to, że mamy do czynienia z relacją równoważności.

Abstrahując jednak od matematycznej nomenklatury, oznacza to po prostu, że przedmioty da się podzielić na rozłączne zbiory (nazywane klasami abstrakcji), takie że dwa przedmioty są nieporównywalne wtedy i tylko wtedy, gdy należą do tego samego zbioru.

Udowodnijmy ponadto, że przedmioty należące do tej samej klasy abstrakcji tworzą spójny przedział wag. Weźmy trzy przedmioty o masach oraz takie że oraz przedmioty o masach i są nieporównywalne. Wystarczy pokazać, że przedmiot o masie jest nieporównywalny z przedmiotem o masie Nie zmieniając instancji problemu z punktu widzenia Bajtazara, możemy zmienić masę pierwszego przedmiotu na a trzeciego na Zachęcamy czytelnika do sprawdzenia, iż wskazanie wagi dla dowolnego podzbioru przedmiotów pozostanie po tej zmianie takie samo.

Możemy teraz trochę poprawić nasz algorytm. Najpierw posortujmy przedmioty ze względu na ich masy, a następnie dla każdej pary kolejnych stwierdźmy, czy są one porównywalne. Wystarcza to do wyznaczenia rozmiarów klas abstrakcji, a w szczególności również szukanej liczby par. Otrzymujemy w ten sposób algorytm działający w czasie

Jednak taka złożoność nadal nie wystarcza. Można ją poprawić, używając techniki nazywanej "Plecak bez jednego". Dla każdej pary kolejnych przedmiotów chcemy otrzymać tablicę programowania dynamicznego z dodanymi wszystkimi pozostałymi przedmiotami. Zdefiniujmy rekurencyjną procedurę obliczającą wyniki dla par przedmiotów o indeksach z przedziału mając daną tablicę programowania dynamicznego dla przedmiotów spoza danego przedziału. Niech Najpierw zaktualizujmy o przedmioty z przedziału i wykonajmy rekurencyjnie dla przedziału Następnie pierwotne zaktualizujmy o przedmioty z przedziału i wykonajmy rekurencyjnie dla przedziału Obliczmy również wynik dla pary przedmiotów o indeksach oraz osobno aktualizując o wszystkie pozostałe przedmioty. Czas działania opisuje następujące równanie rekurencyjne Rozwiązując je, dochodzimy do wniosku, iż złożoność czasowa naszego ostatecznego algorytmu wynosi