Analiza

Zadatkom je dato ukupno ~N~ kutija i ~M~ predmeta, pri čemu svaka kutija ima neku svoju nosivost, dok svaki predmet ima neku svoju težinu i određenu vrednost. Takođe, ključna stavka u postavci zadatka jeste ograničenje da je u jednu kutiju moguće smestiti tačno jedan predmet i to samo ako je nosivost kutije veća od težine predmeta.

Prethodnim je svaki predmet definisan jednim uređenim parom (težina, vrednost), dok je svaka kutija definisana svojom nosivošću. Najpre, radi efikasnijeg rešavanja zadatka sortirati i kutije i predmete u neopadajućem redosledu prema njihovoj nosivosti, odnosno težini, respektivno. Ove operacije lako se izvode u ukupnoj vremenskoj složenosti ~\mathcal{O}(M\log M)+\mathcal{O}(N\log N)~ ukoliko se koristi neki napredniji algoritam sortiranja.

Zatim, polazeći od kutije sa najnižom nosivošću, proveriti koji sve predmeti su lakši od njene nosivosti i odabrati predmet sa najvišom vrednošću. Pri svakoj narednoj iteraciji takođe je neophodno proveravati koje je predmete moguće poneti određenom kutijom i birati uvek predmet čija je vrednost najveća. Kako su kutije sortirane po nosivosti, a predmeti po težini, svakom sledećom kutijom biće izvodljivo poneti svaki od predmeta koji bilo moguće poneti i onom niže nosivosti i eventualno još poneki.

Lako se dokazuje da se do najveće zbirne vrednosti predmeta prenosive zadatim kutijama dolazi tako što se u svakoj iteraciji bira najvredniji predmet koji je prema njegovoj težini u datu kutiju moguće smestiti, naravno krećući se od kutije sa najnižom ka kutiji sa najvišom nosivošću. Predmeti koji zadovoljavaju uslov da im je težina niža od nosivosti trenutne kutije potrebno je čuvati unutar neke strukture podataka iz koje se na efikasniji način od puke linearne pretrage može pronaći i izvući baš onaj član sa najvišom vrednošću.

Konkretno, jedna od takvih apstraktnih struktura podataka jeste prioritetni red (eng. priority queue), koji se obično implementira preko takozvane hrpe (eng. heap), a koji na račun logaritamske složenosti umetanja proizvoljnog elementa dozvoljava vađenje člana sa maksimalnom vrednošću takođe u logaritamskoj vremenskoj složenosti po broju elemenata.

Smernice za algoritam

Nakon sortiranja kutija po nosivosti i predmeta po težini, inicijalizovati rezultat koji predstavlja ukupnu sumu vrednosti predmeta na nulu. U petlji prolaziti kroz kutije počevši od one sa najnižom ka onoj sa najvišom nosivošću i u svakom prolasku ispitivati koji sve predmeti imaju nižu težinu od nosivosti trenutne kutije i dodavati ih u prioritetni red prema njihovoj vrednosti. Na kraju iteracije izvaditi iz reda predmet sa najvišom vrednošću i njegovu vrednost sabrati s trenutnim rezultatom. Po izlasku iz petlje ispisati rezultat. Nije teško pokazati da je asimptotska vremenska složenost ovakvog algoritma loglinearna ~\mathcal{O}(M\log M)+\mathcal{O}(N\log N)~, odnosno asimptotski jednaka sortiranju ulaznih vrednosti.